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

DOI10.1016/0166-218X(90)90021-4zbMath0679.68077OpenAlexW1976791953MaRDI QIDQ1822965

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 analysissubset-sumpolynomial approximation schemes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Two linear approximation algorithms for the subset-sum problem ⋮ Approximation algorithms for knapsack problems with cardinality constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation schemes for the subset-sum problem: Survey and experimental analysis
• Worst-case analysis of an approximation scheme for the subset-sum problem
• Approximation algorithms for combinatorial problems
• Time bounds for selection
• Worst-case analysis of greedy algorithms for the subset-sum problem
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

This page was built for publication: A new linear storage, polynomial-time approximation scheme for the subset-sum problem