Skip to main content
Article
Heuristic Algorithms for Balanced Multi-way Number Partitioning
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11: Barcelona, Catalonia, Spain, 16 - 22 July 2011
  • Jilian ZHANG, Singapore Management University
  • Kyriakos MOURATIDIS, Singapore Management University
  • Hwee Hwa PANG, Singapore Management University
Publication Type
Conference Proceeding Article
Version
submittedVersion
Publication Date
7-2011
Abstract

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.

Keywords
  • Approximate algorithms,
  • Cardinalities,
  • Exact algorithms,
  • Heuristic techniques,
  • Novel strategies,
  • Number distribution,
  • Number partitioning,
  • Subset sum
ISBN
9781577355137
Identifier
10.5591/978-1-57735-516-8/IJCAI11-122
Publisher
AAAI Press
City or Country
Menlo Park, CA
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Additional URL
http://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-122
Citation Information
Jilian ZHANG, Kyriakos MOURATIDIS and Hwee Hwa PANG. "Heuristic Algorithms for Balanced Multi-way Number Partitioning" Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11: Barcelona, Catalonia, Spain, 16 - 22 July 2011 (2011) p. 693 - 698
Available at: http://works.bepress.com/kyriakos_mouratidis/35/