---
title: "A Hybrid Recursive Multi-Way Number Partitioning Algorithm"
authors:
  - "Richard E. Korf"
doi: "10.5591/978-1-57735-516-8/IJCAI11-106"
url: "https://ijcai.org/proceedings/2011/106"
pdf: "https://ijcai.org/proceedings/2011/0106.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "591-595"
track: ""
keywords:
---

# A Hybrid Recursive Multi-Way Number Partitioning Algorithm

Richard E. Korf

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 591-595. DOI: [10.5591/978-1-57735-516-8/IJCAI11-106](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.