The primal and dual greedy algorithms for the knapsack problem: the average behavior (Q2773680)

The average behavior of the primal and dual greedy algorithms is analyzed. In practice greedy algorithms can work rather good despite the pessimistic conclusions of the worst-case analysis. Consider the simplest 0-1 knapsack problem. Suppose that the weights and values of the items are positive random variables and the knapsack capacity is \(\lambda*n\), where \(n\) is the item number and \(\lambda\) is an arbitrary positive number. Say that an algorithm has asymptotic error \(t\) if the solution obtained by this algorithm differs from the optimal one at most by \(t\) in the probability tending to \(1\) as \(n\) grows. Then the primal and dual greedy algorithms have asymptotic error \(t\) whenever \(1/2-t/3<\lambda\).