Analysis of the Karmarkar-Karp Differencing Algorithm - Computer Science > Numerical AnalysisReport as inadecuate




Analysis of the Karmarkar-Karp Differencing Algorithm - Computer Science > Numerical Analysis - Download this document for free, or read online. Document in PDF available to download.

Abstract: The Karmarkar-Karp differencing algorithm is the best known polynomial timeheuristic for the number partitioning problem, fundamental in both theoreticalcomputer science and statistical physics. We analyze the performance of thedifferencing algorithm on random instances by mapping it to a nonlinear rateequation. Our analysis reveals strong finite size effects that explain why theprecise asymptotics of the differencing solution is hard to establish bysimulations. The asymptotic series emerging from the rate equation satisfiesall known bounds on the Karmarkar-Karp algorithm and projects a scaling$n^{-c\ln n}$, where $c=1-2\ln2=0.7213

.$. Our calculations reveal subtlerelations between the algorithm and Fibonacci-like sequences, and we establishan explicit identity to that effect.



Author: Stefan Boettcher, Stephan Mertens

Source: https://arxiv.org/







Related documents