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

James Calvin, Joseph Leung

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

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 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., a 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]2 and Kn = σn for some constant 0 < σ < 1/2, we show that √n(PL - PDDG) converges in distribution.

Original languageEnglish (US)
Pages (from-to)202-210
Number of pages9
JournalOperations Research Letters
Volume31
Issue number3
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Average-case analysis of a greedy algorithm for the 0/1 knapsack problem'. Together they form a unique fingerprint.

Cite this