# Analysis of the Karmarkar-Karp Differencing Algorithm - Computer Science > Numerical Analysis

Analysis of the Karmarkar-Karp Differencing Algorithm - Computer Science > Numerical Analysis - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Stefan Boettcher, Stephan Mertens

Fuente: https://arxiv.org/