
We 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 = 0(1) constraints as the number of variables grows. We show that results on the single-constraint problem can be extended to this situation. Chiefly, we generalise a result of Lueker on the duality gap, and a result of Goldberg/Marchetti-Spaccamela on exact solvability. In the latter case, our methods differ markedly from those for the single-constraint result.
Stochastic programming, Integer programming, Boolean programming, probabilistic analysis, 0-1 knapsack problem
Stochastic programming, Integer programming, Boolean programming, probabilistic analysis, 0-1 knapsack problem
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 22 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
