Average-case analysis of a greedy algorithm for the 0/1 knapsack problem

We consider the average-case performance of a well-known approximation algorithm for the 0/1 knapsack problem, the decreasing density greedy (DDG) algorithm. Let Un={u1,....,un} be a set of n items, with each item ui having a size si and a profit pi, and Kn be the capacity of the knapsack. Given an instance of the 0/1 knapsack problem, let PL denote the total profit of an optimal solution of the linear version of the problem (i.e., fraction of an item can be packed in the knapsack) and PDDG denote the total profit of the solution obtained by the DDG algorithm. Assuming that Un is a random sample from the uniform distribution over (0, 1)]² and Kn=σn of some constant 0<σ<1/2, we show that √(n)(PL – PDDG) converges in distribution.