Expectation analysis for bounding solutions of the 0–1 knapsack problem

In this paper, an entirely novel discrete probabilistic model is presented to generate 0–1 Knapsack Problem instances. We analyze the expected behavior of the greedy algorithm, the eligible-first algorithm and the linear relaxation algorithm for these instances; all used to bound the solution of the 0–1 Knapsack Problem (0–1 KP) and/or its approximation. The probabilistic setting is given and the main random variables are identified. The expected performance for each of the aforementioned algorithms is analytically established in closed forms in an unprecedented way.