Average behavior of greedy algorithms for the minimization knapsack problem: General coefficient distributions

For the minimization knapsack problem with Boolean variables, primal and dual greedy algorithms are formally described. Their relations to the corresponding algorithms for the maximization knapsack problem are shown. The average behavior of primal and dual algorithms for the minimization problem is analyzed. It is assumed that the coefficients of the objective function and the constraint are independent identically distributed random variables on [0, 1] with an arbitrary distribution having a density and that the right-hand side d is deterministic and proportional to the number of variables (i.e., d = μn). A condition on μ is found under which the primal and dual greedy algorithms have an asymptotic error of t.