hide
Free keywords:
-
Abstract:
We present the first average-case analysis proving a polynomial upper bound
on the expected running time of an exact algorithm for the 0/1 knapsack problem.
In particular, we prove for various input distributions, that the number of
Pareto-optimal knapsack fillings is polynomially bounded in the number of availa
ble items.
An algorithm by Nemhauser and Ullmann can enumerate these solutions very
efficiently so that a polynomial upper bound on the number of Pareto-optimal sol
utions
implies an algorithm with expected polynomial running time.
The random input model underlying our analysis is quite general
and not restricted to a particular input distribution. We assume adversarial
weights and randomly drawn profits (or vice versa). Our analysis covers general
probability
distributions with finite mean and, in its most general form, can even
handle different probability distributions for the profits of different items.
This feature enables us to study the effects of correlations between profits
and weights. Our analysis confirms and explains practical studies showing
that so-called \em strongly correlated\/} instances are harder to solve than
{\em weakly correlated\/ ones.
