A Hybrid Recursive Multi-Way Number Partitioning Algorithm
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.
Cite
Text
Korf. "A Hybrid Recursive Multi-Way Number Partitioning Algorithm." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-106Markdown
[Korf. "A Hybrid Recursive Multi-Way Number Partitioning Algorithm." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/korf2011ijcai-hybrid/) doi:10.5591/978-1-57735-516-8/IJCAI11-106BibTeX
@inproceedings{korf2011ijcai-hybrid,
title = {{A Hybrid Recursive Multi-Way Number Partitioning Algorithm}},
author = {Korf, Richard E.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {591-596},
doi = {10.5591/978-1-57735-516-8/IJCAI11-106},
url = {https://mlanthology.org/ijcai/2011/korf2011ijcai-hybrid/}
}