## Abstract

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 U_{n} = {u_{1},⋯, u_{n}} be a set of n items, with each item u_{i} having a size s_{i} and a profit p_{i}, and K_{n} be the capacity of the knapsack. Given an instance of the 0/1 knapsack problem, let P_{L} denote the total profit of an optimal solution of the linear version of the problem (i.e., a fraction of an item can be packed in the knapsack) and P_{DDG} denote the total profit of the solution obtained by the DDG algorithm. Assuming that U_{n} is a random sample from the uniform distribution over (0,1]^{2} and K_{n} = σn for some constant 0 < σ < 1/2, we show that √n(P_{L} - P_{DDG}) converges in distribution.

Original language | English (US) |
---|---|

Pages (from-to) | 202-210 |

Number of pages | 9 |

Journal | Operations Research Letters |

Volume | 31 |

Issue number | 3 |

DOIs | |

State | Published - May 1 2003 |

## All Science Journal Classification (ASJC) codes

- Software
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics

## Keywords

- 0/1 Knapsack
- Approximation algorithms
- NP-hard
- Probabilistic analysis