A new linear storage, polynomial-time approximation scheme for the subset-sum problem

DOI10.1016/0166-218X(90)90021-4MaRDI QIDQ1822965zbMATH OpenOpenAlexFDO

Authors Matteo Fischetti

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(90)90021-4

zbMATH Keywords

computational analysispolynomial approximation schemessubset-sum

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A polynomial approximation scheme for the subset sum problem
• scientific article; zbMATH DE number 1104339
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Two linear approximation algorithms for the subset-sum problem
• A Fast Approximation Algorithm For The Subset-Sum Problem

Cites work

• Approximation algorithms for combinatorial problems
• Approximation schemes for the subset-sum problem: Survey and experimental analysis
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• scientific article; zbMATH DE number 3694944 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Time bounds for selection
• Worst-case analysis of an approximation scheme for the subset-sum problem
• Worst-case analysis of greedy algorithms for the subset-sum problem

Cited in

(7)

• A polynomial approximation scheme for the subset sum problem
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Approximation algorithms for knapsack problems with cardinality constraints
• A new fully polynomial time approximation scheme for the interval subset sum problem
• Two linear approximation algorithms for the subset-sum problem
• Techniques for solving subset sum problems within a given tolerance
• scientific article; zbMATH DE number 1104339 (Why is no real title available?)

This page was built for publication: A new linear storage, polynomial-time 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 Q1822965)