A Hybrid Recursive Multi-Way Number Partitioning Algorithm

Korf, Richard E.

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

A Hybrid Recursive Multi-Way Number Partitioning Algorithm

Richard E. Korf

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 591-595.

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

Abstract

The number partitioning problem is to divide a given set of N positive integers into K subsets, so that the sum of the numbers in each subset are as nearly equal as possible. While effective algorithms for two-way partitioning exist, multi-way partitioning is much more challenging. We introduce an improved algorithm for optimal multi-way partitioning, by combining several existing algorithms with some new extensions. We test our algorithm for partitioning 31-bit integers from three to ten ways, and demonstrate orders of magnitude speedup over the previous state of the art.

Richard E. Korf. 2011. A Hybrid Recursive Multi-Way Number Partitioning Algorithm. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 591–595. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-106

@inproceedings{ijcai2011p106,
  title     = {A Hybrid Recursive Multi-Way Number Partitioning Algorithm},
  author    = {Korf, Richard E.},
  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     = {591--595},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-106},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-106},
}

TY  - CPAPER
TI  - A Hybrid Recursive Multi-Way Number Partitioning Algorithm
AU  - Korf, Richard E.
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  - 591
EP  - 595
DO  - 10.5591/978-1-57735-516-8/IJCAI11-106
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-106
ER  -