Worst-case analysis of greedy algorithms for the subset-sum problem

DOI10.1007/BF02612360zbMath0527.90072OpenAlexW2042388408MaRDI QIDQ3042877

Silvano Martello, Paolo Toth

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02612360

zbMATH Keywords

worst-case performancegreedy algorithmspolynomial approximation schemesubset-sum problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Boolean programming (90C09)

Related Items (12)

Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem ⋮ Worst-case analysis of an approximation scheme for the subset-sum problem ⋮ A new enumeration scheme for the knapsack problem ⋮ A polynomial approximation scheme for the subset sum problem ⋮ An efficient fully polynomial approximation scheme for the Subset-Sum problem. ⋮ Two linear approximation algorithms for the subset-sum problem ⋮ A note on 0.5-bounded greedy algorithms for the 0/1 knapsack problem ⋮ Dynamic scheduling of batch-processing machines with non-identical product sizes ⋮ The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem ⋮ A new linear storage, polynomial-time approximation scheme for the subset-sum problem ⋮ Average-case performance of rollout algorithms for knapsack problems ⋮ Approximation schemes for the subset-sum problem: Survey and experimental analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• Fast Approximation Algorithms for Knapsack Problems
• Worst-Case Analysis of Heuristic Algorithms
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem

This page was built for publication: Worst-case analysis of greedy algorithms for the subset-sum problem