Approximation schemes for the subset-sum problem: Survey and experimental analysis

DOI10.1016/0377-2217(85)90115-8zbMath0583.90070OpenAlexW2012468431MaRDI QIDQ1069445

Paolo Toth, Silvano Martello

Publication date: 1985

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(85)90115-8

zbMATH Keywords

heuristicscomputational experimentssubset-sum problempolynomial approximation schemes

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items

An efficient fully polynomial approximation scheme for the Subset-Sum problem., Minimizing makespan subject to minimum flowtime on two identical parallel machines, 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, Heuristic methods and applications: A categorized survey

Cites Work

• Unnamed Item
• Probabilistic analysis of the subset-sum problem
• Approximation algorithms for combinatorial problems
• Worst-case analysis of greedy algorithms for the subset-sum problem
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• Fast Approximation Algorithms for Knapsack Problems
• Hard Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems