hide
Free keywords:
-
Abstract:
The size of the Pareto curve for the bicriteria version of the knapsack
problem is polynomial on average. This has been shown for various random input
distributions. We experimentally investigate the number of Pareto points for
knapsack instances over $n$ elements whose profits and weights are chosen at
random according to various classes of input distributions. The numbers
observed in our experiments are significantly smaller than the known upper
bounds. For example, the upper bound for so-called uniform instances is
$O(n^3)$. Based on our experiments, we conjecture that the number of Pareto
points for these instances is only $\Theta(n^2)$. We also study other
structural properties for random knapsack instances that have been used in
theoretical studies to bound the average-case complexity of the knapsack
problem.
Furthermore, we study advanced algorithmic techniques for the knapsack
problem. In particular, we review several ideas that originate from theory as
well as from practice. Most of the concepts that we use are simple and have
been known since at least 20 years, but apparently have not been used in this
combination. Surprisingly, the result of our study is a very competitive code
that outperforms the best previous implementation \emph{Combo} by orders of
magnitude for various classes of random instances, including harder random
knapsack instances in which profits and weights are chosen in a correlated
fashion.
