Heuristic Algorithms for Balanced Multi-Way Number Partitioning

Zhang, Jilian; Mouratidis, Kyriakos; Pang, HweeHwa

doi:10.5591/978-1-57735-516-8/IJCAI11-122

Heuristic Algorithms for Balanced Multi-Way Number Partitioning

Jilian Zhang, Kyriakos Mouratidis, HweeHwa Pang

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 693-697.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-122

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.

Jilian Zhang, Kyriakos Mouratidis, and HweeHwa Pang. 2011. Heuristic Algorithms for Balanced Multi-Way Number Partitioning. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 693–697. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-122

@inproceedings{ijcai2011p122,
  title     = {Heuristic Algorithms for Balanced Multi-Way Number Partitioning},
  author    = {Zhang, Jilian and Mouratidis, Kyriakos and Pang, HweeHwa},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {693--697},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-122},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-122},
}

TY  - CPAPER
TI  - Heuristic Algorithms for Balanced Multi-Way Number Partitioning
AU  - Zhang, Jilian
AU  - Mouratidis, Kyriakos
AU  - Pang, HweeHwa
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 693
EP  - 697
DO  - 10.5591/978-1-57735-516-8/IJCAI11-122
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-122
ER  -