ALCOMFT-TR-03-60

Rene Beier and Berthold V\"ocking
Probabilistic Analysis of Knapsack Core Algorithms
MPI. Work package 4. October 2003.

Abstract: We study the average-case performance of algorithms for the binary knapsack problem. Our focus lies on the analysis of so-called knapsack core algorithms, the predominant algorithmic concept used in practice. Core algorithms start with the computation of an optimal fractional solution that contains at most one variable has a fractional value, and then exchange items until an optimal integral solution is found. The idea is that in many cases the optimal integral solution should be close to the fractional one such that only few items need to be exchanged. Despite the well known hardness of the knapsack problem on worst-case instances, practical studies show that knapsack core algorithms can solve large scale instances very efficiently. For example, they exhibit almost linear running time on purely random inputs.

In this paper, we present the first theoretical result on the running time of core algorithms that comes close to the results observed in practice. We prove an upper bound of n \polylog(n) on the expected running time for random instances with n item and uniformly random profits and weights. This significantly improves a previous bound of O(n⁴) for such instances. This analysis is based on a different algorithmic concept, however. The previously best known upper bound for the running time of a core algorithm is polynomial as well, but the degree of the polynomial is at least a large three digit number. In addition to uniformly random instances, we investigate harder instances in which profits and weights are correlated. Here we can prove a tradeoff describing how the correlation between profits and weights influences the running time.

Postscript file: ALCOMFT-TR-03-60.ps.gz (89 kb).