Estimating the Work in Integer Partitioning

Published

January 31, 2003

Author(s)

April Andreas, Isabel M. Beichl

Abstract

For a given set of numbers, the integer partitioning problem is to divide the numbers into two groups, so that the sums of the numbers in each group differ by the smallest amount possible. In a balanced perfect partition, the sums differ by only zero or one, and the numbers of elements in each group differ by only zero or one. This problem is known to be NP-complete [3], and as a result, heuristics have been developed that provide minimized partition[6] and cardinality[7] differences over time. It is not clear, however, how long these heuristics need to be run to find an acceptable answer. We have developed a method to estimate the amount of work required to fine an optimal solution to the problem. We have also developed a method to estimate how many balanced perfect partitions exist. We use a variation of a technique developed by Knuth for estimating the size of backtrack trees [5].

Citation

Computing in Science & Engineering

Volume

5

Issue

9

Pub Type

Journals

Download Paper

Local Download

Keywords

algorithms, integer partition, load balancing, Monte Carlo methods

Citation

Andreas, A. and Beichl, I. (2003), Estimating the Work in Integer Partitioning, Computing in Science & Engineering, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50977 (Accessed April 26, 2024)