https://doi.org/10.1140/epjb/e2008-00320-9
Analysis of the Karmarkar-Karp differencing algorithm
1
Department of Physics, Emory University, Atlanta GA 30322-2430, USA
2
Institut für Theoretische Physik, Otto-von-Guericke Universität, PF 4120, 39016 Magdeburg, Germany
3
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
Corresponding author: a sboettc@emory.edu
Received:
27
February
2008
Revised:
7
May
2008
Published online:
9
August
2008
The Karmarkar-Karp differencing algorithm is the best known
polynomial time heuristic for the number partitioning problem,
fundamental in both theoretical computer science and statistical
physics. We analyze the performance of the differencing algorithm on
random instances by mapping it to a nonlinear rate equation. Our
analysis reveals strong finite size effects that explain why the
precise asymptotics of the differencing solution is hard to
establish by simulations. The asymptotic series emerging from the
rate equation satisfies all known bounds on the Karmarkar-Karp
algorithm and projects a scaling , where
c = 1/(2 ln 2)=0.7213.... Our calculations reveal subtle relations
between the algorithm and Fibonacci-like sequences, and we establish
an explicit identity to that effect.
PACS: 02.60.Pn – Numerical optimization / 89.75.Da – Systems obeying scaling laws / 89.75.Fb – Structures and organization in complex systems
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2008