CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Algorithm for Linear Number Partitioning into Maximum Number of Subsets

by Hussain Md. Mehedul Islam, Mohammad Obaidur Rahman
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 54 - Number 10
Year of Publication: 2012
Authors: Hussain Md. Mehedul Islam, Mohammad Obaidur Rahman
10.5120/8606-2376

Hussain Md. Mehedul Islam, Mohammad Obaidur Rahman . Algorithm for Linear Number Partitioning into Maximum Number of Subsets. International Journal of Computer Applications. 54, 10 ( September 2012), 41-46. DOI=10.5120/8606-2376

@article{ 10.5120/8606-2376,
author = { Hussain Md. Mehedul Islam, Mohammad Obaidur Rahman },
title = { Algorithm for Linear Number Partitioning into Maximum Number of Subsets },
journal = { International Journal of Computer Applications },
issue_date = { September 2012 },
volume = { 54 },
number = { 10 },
month = { September },
year = { 2012 },
issn = { 0975-8887 },
pages = { 41-46 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume54/number10/8606-2376/ },
doi = { 10.5120/8606-2376 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:55:21.940322+05:30
%A Hussain Md. Mehedul Islam
%A Mohammad Obaidur Rahman
%T Algorithm for Linear Number Partitioning into Maximum Number of Subsets
%J International Journal of Computer Applications
%@ 0975-8887
%V 54
%N 10
%P 41-46
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The number partitioning problem is to decide whether a given multiset of integers can be partitioned into two "halves" of given cardinalities such that the discrepancy, the absolute value of the difference of their sums, is minimized. While Partitioning problem is known to be NP-complete, only few studies have investigated on its variations. While lots of investigation has been made for two-way partitioning, only a few have for multi-way partitioning, while most of them are not feasible for real time environment. We introduce an improved multi-way partitioning algorithm feasible for real time which returns maximum number of subset can be made based on the order of the numbers as they appear.

References
  1. S. Mertens, "The Easiest Hard Problem: Number Partitionin,"A. G. Percus, G. Istrate and C. Moore, eds. , Computational Complexity and Statistical Physics (Oxford University Press, New York, 2006), p. 125-139.
  2. Michael R. Garey and David S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1997.
  3. E. Coman and G. S. Lueker, "Probabilistic Analysis of Packing and Partitioning Algorithms,"(John Wiley & Sons, New York, 1991).
  4. Walsh, "Where are the really hard manipulation problems? The phase transition in manipulating the veto rule," IJCAI-09, p. 324–329.
  5. Richard E. Korf, "Objective functions for multi-way number partitioning," Symposium on Combinatorial Search (SOCS-10), ATLANTA, GA-2010.
  6. Richard E. Korf, "A complete anytime algorithm for number partitioning," Arti?cial Intelligence, paper 106(2), p. 181–203, 1998.
  7. Richard Korf, "A Hybrid Recursive Multi-Way Number Partitioning Algorithm" on Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI, Spain, July 16-22, 2011.
  8. The Wikipedia Website. [Online]. Available: http://en. wikipedia. org/wiki/Partition_problem
  9. The Department of Computing Science - Umeå University website [online]. Available: http://www8. cs. umu. se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45. HTM
  10. Karmarkar and Karp, "The differencing method of set partitioning," Technical Report UCB/CSD 82/113, Computer Science Division, University of California, Berkeley, 1982.
  11. S. Mertens, "A complete anytime algorithm for balanced number partitioning," arXiv. org/abs/cs. DS/9903011.
Index Terms

Computer Science
Information Sciences

Keywords

Anytime algorithm Greedy heuristic Linear partitioning NP-completeness Partitioning problem

Powered by PhDFocusTM