Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Estimating the Work in Integer Partitioning

Published

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

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 15, 2024)
Created January 30, 2003, Updated October 12, 2021