




A complete anytime algorithm for balanced number partitioning
Abstract
Given a set of numbers, the balanced partioning problem is to divide them into
two subsets, so that the sum of the numbers in each subset are as nearly equal
as possible, subject to the constraint that the cardinalities of the subsets
be within one of each other. We combine the balanced largest differencing
method (BLDM) and Korf's complete KarmarkarKarp algorithm to get a new
algorithm that optimally solves the balanced partitioning problem. For
numbers with twelve significant digits or less, the algorithm can optimally
solve balanced partioning problems of arbitrary size in practice. For numbers
with greater precision, it first returns the BLDM solution, then continues to
find better solutions as time allows.
BiBTeX Entry
@misc{, author = {Stephan Mertens}, title = {A complete anytime algorithm for balanced number partitioning}, year = {1999}, note = {\url{http://arXiv.org/abs/cs.DS/9903011}} }
Download:
cckk.ps.gz (gzip'ed postscript, 91 k)





© by Stephan Mertens
URL: http://
updated on Wednesday, November 05th 2003, 13:54:08 CET;