Conference Proceeding Article
Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for skewed number distributions. A combination of LRM and Meld leads to a heuristic technique that consistently achieves a narrower spread of subset sums than BLDM.
Approximate algorithms, Cardinalities, Exact algorithms, Heuristic techniques, Novel strategies, Number distribution, Number partitioning, Subset sum
Databases and Information Systems | Theory and Algorithms
Data Management and Analytics
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11: Barcelona, Catalonia, Spain, 16 - 22 July 2011
City or Country
Menlo Park, CA
ZHANG, Jilian; MOURATIDIS, Kyriakos; and PANG, Hwee Hwa.
Heuristic Algorithms for Balanced Multi-way Number Partitioning. (2011). Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11: Barcelona, Catalonia, Spain, 16 - 22 July 2011. 693-698. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1359
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.