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

James M. Calvin; Joseph Leung

doi:10.1016/S0167-6377(02)00222-5

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

James M. Calvin, Joseph Leung

Computer Science

Research output: Contribution to journal › Article › peer-review

11 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 U_n = {u₁,⋯, 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]² 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	https://doi.org/10.1016/S0167-6377(02)00222-5
State	Published - May 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

Access to Document

10.1016/S0167-6377(02)00222-5

Cite this

@article{048964f875794b9b9eb317a06446bf23,

title = "Average-case analysis of a greedy algorithm for the 0/1 knapsack problem",

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.",

keywords = "0/1 Knapsack, Approximation algorithms, NP-hard, Probabilistic analysis",

author = "Calvin, {James M.} and Joseph Leung",

year = "2003",

month = may,

doi = "10.1016/S0167-6377(02)00222-5",

language = "English (US)",

volume = "31",

pages = "202--210",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

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

AU - Calvin, James M.

AU - Leung, Joseph

PY - 2003/5

Y1 - 2003/5

N2 - 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.

AB - 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.

KW - 0/1 Knapsack

KW - Approximation algorithms

KW - NP-hard

KW - Probabilistic analysis

UR - http://www.scopus.com/inward/record.url?scp=0037402226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037402226&partnerID=8YFLogxK

U2 - 10.1016/S0167-6377(02)00222-5

DO - 10.1016/S0167-6377(02)00222-5

M3 - Article

AN - SCOPUS:0037402226

SN - 0167-6377

VL - 31

SP - 202

EP - 210

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this