Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems

DOI10.1016/0167-6377(93)90072-OzbMath0798.90109MaRDI QIDQ1319674

Tsung-Chyan Lai

Publication date: 12 April 1994

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

zbMATH Keywords

greedy algorithmNP-hardnesspartition problemworst-case performance ratiosubset-sum problemunbounded knapsack problem

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items (6)

Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations ⋮ Two linear approximation algorithms for the subset-sum problem ⋮ On the Complexity of Minimizing the Total Calibration Cost ⋮ Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem ⋮ Unnamed Item ⋮ A linear compound algorithm for uniform machine scheduling

Cites Work

• Unnamed Item
• Heuristic algorithms for the multiple knapsack problem
• Worst-case analysis of the differencing method for the partition problem
• Worst-Case Analysis of Heuristic Algorithms
• Reducibility among Combinatorial Problems

This page was built for publication: Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems