Probabilistic analysis of the multidimensional knapsack problem

The authors analyse the multi-constraint zero-one knapsack problem, under the assumption that all coefficients are drawn from a uniform [0,1] distribution and there are m=O(1) constraints as the number of variables grows. They show that results on the single-constraint problem can be extended to this situation. Chiefly, the authors generalise a result of Lucker on the duality gap, and a result of Goldberg/Marchetti-Spaccamela on exact solvability. In the latter case, the present methods differ markedly from those for the single-constraint result.