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

DOI10.1016/S0167-6377(02)00222-5zbMath1064.90026OpenAlexW2041429356MaRDI QIDQ1811628

Joseph Y.-T. Leung, James M. Calvin

Publication date: 17 June 2003

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(02)00222-5

zbMATH Keywords

probabilistic analysisNP-hardapproximation algorithms0/1 knapsack

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (1)

Average-case performance of rollout algorithms for knapsack problems

Cites Work

• A probabilistic analysis of the multiknapsack value function
• On rates of convergence and asymptotic normality in the multiknapsack problem
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• Average-Case Analysis of Off-Line and On-Line Knapsack Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.