An efficient fully polynomial approximation scheme for the Subset-Sum problem.

DOI10.1016/S0022-0000(03)00006-0MaRDI QIDQ1400576zbMATH OpenWikidataFDO

Authors Hans Kellerer, Renata Mansini, Ulrich Pferschy, Maria Grazia Speranza

Publication date 13 August 2003

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-0000(03)00006-0

zbMATH Keywords

Fully polynomial approximation schemeKnapsack problemSubset-sum problemWorst-case performance

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1104339
• A Fast Approximation Algorithm For The Subset-Sum Problem
• 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
• A polynomial approximation scheme for the subset sum problem

Cites work

• A Fast Approximation Algorithm For The Subset-Sum Problem
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• 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
• Hard Knapsack Problems
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3694944 (Why is no real title available?)
• scientific article; zbMATH DE number 3698707 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3575633 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1104339 (Why is no real title available?)
• scientific article; zbMATH DE number 910857 (Why is no real title available?)
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Worst-case analysis of greedy algorithms for the subset-sum problem

Cited in

(39)

• Priority algorithms for the subset-sum problem
• A polynomial approximation scheme for the subset sum problem
• Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
• A new fully polynomial time approximation scheme for the interval subset sum problem
• Robust single machine scheduling with a flexible maintenance activity
• Scheduling with time-of-use costs
• Exact and approximation algorithms for geometric and capacitated set cover problems
• Optimal parallel machines scheduling with availability constraints
• A new linear storage, polynomial-time approximation scheme for the subset-sum problem
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Preemptive scheduling on two identical parallel machines with a single transporter
• Approximation schemes for subset-sums ratio problems
• Approximating subset sum ratio via subset sum computations
• Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Some complexity and approximation results for coupled-tasks scheduling problem according to topology
• Online and semi-online scheduling on capacitated two-parallel machines
• A Fast Approximation Algorithm for the Subset-sum Problem
• Coupled-tasks in presence of bipartite compatibilities graphs
• Techniques for solving subset sum problems within a given tolerance
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
• A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
• A Fast Approximation Algorithm For The Subset-Sum Problem
• scientific article; zbMATH DE number 1104339 (Why is no real title available?)
• Space-efficient approximations for subset sum
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)
• A subquadratic approximation scheme for partition
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• An exact algorithm for the subset sum problem
• Approximation algorithms for scheduling with reservations
• An FPTAS for scheduling with resource constraints
• Learning-augmented algorithms for online subset sum
• Approximating subset sum ratio via partition computations
• Single machine scheduling with semi-resumable machine availability constraints
• On tractable convex relaxations of standard quadratic optimization problems under sparsity constraints
• Exploring the approximability landscape of 3SUM
• Partitioning problems with splittings and interval targets
• Does subset sum admit short proofs?
• Weakly approximating knapsack in subquadratic time

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: An efficient fully polynomial 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 Q1400576)