An efficient approximation scheme for the subset-sum problem

DOI10.1007/3-540-63890-3_42MaRDI QIDQ4370212zbMATH OpenFDO

Authors Hans Kellerer, Ulrich Pferschy, Maria Grazia Speranza

Publication date 14 January 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63890-3_42

zbMATH Keywords

fully polynomial approximation schemesubset-sum problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A Fast Approximation Algorithm For The Subset-Sum Problem
• A new linear storage, polynomial-time approximation scheme for the subset-sum problem
• A polynomial approximation scheme for the subset sum problem

Cited in

(26)

• Parallel approximation schemes for subset sum and knapsack problems
• Worst-case analysis of an approximation scheme for the subset-sum problem
• A polynomial approximation scheme for the subset sum problem
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A 3/4-approximation algorithm for multiple subset sum
• Approximation algorithms for knapsack problems with cardinality constraints
• A new fully polynomial time approximation scheme for the interval subset sum problem
• A new linear storage, polynomial-time approximation scheme for the subset-sum problem
• Two linear approximation algorithms for the subset-sum problem
• Approximation algorithms for the three-machine proportionate mixed shop scheduling
• Constant time approximation scheme for largest well predicted subset
• Saving space by algebraization
• Approximability of the Subset Sum Reconfiguration Problem
• The subset sum problem
• A Fast Approximation Algorithm for the Subset-sum Problem
• \(O((\log n)^{2})\) time online approximation schemes for bin packing and subset sum problems
• A Fast Approximation Algorithm For The Subset-Sum Problem
• Approximability of the subset sum reconfiguration problem
• Space-efficient approximations for subset sum
• Consistent subsets: computationally feasible methods to compute the Houtman-Maks-index
• An Average-Case Sublinear Exact Li and Stephens Forward Algorithm
• A subquadratic approximation scheme for partition
• A Logarithmic Bound for Solving Subset Sum with P Systems
• LATIN 2004: Theoretical Informatics
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• Algorithms for a two-machine no-wait flow shop scheduling problem with two competing agents

This page was built for publication: An efficient approximation scheme for the subset-sum problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4370212)