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

DOI10.1016/S0022-0000(03)00006-0zbMath1045.68157WikidataQ61638376 ScholiaQ61638376MaRDI QIDQ1400576

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

Publication date: 13 August 2003

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

zbMATH Keywords

Knapsack problemWorst-case performanceFully polynomial approximation schemeSubset-sum problem

Mathematics Subject Classification ID

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

Related Items (25)

Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints ⋮ Coupled-Tasks in Presence of Bipartite Compatibilities Graphs ⋮ Approximation schemes for subset-sums ratio problems ⋮ Approximating subset sum ratio via subset sum computations ⋮ A new fully polynomial time approximation scheme for the interval subset sum problem ⋮ A faster FPTAS for the unbounded knapsack problem ⋮ Unnamed Item ⋮ An FPTAS for scheduling with resource constraints ⋮ Learning-augmented algorithms for online subset sum ⋮ Some complexity and approximation results for coupled-tasks scheduling problem according to topology ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ Preemptive scheduling on two identical parallel machines with a single transporter ⋮ Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance ⋮ Single machine scheduling with semi-resumable machine availability constraints ⋮ ONLINE AND SEMI-ONLINE SCHEDULING ON CAPACITATED TWO-PARALLEL MACHINES ⋮ 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 ⋮ Unnamed Item ⋮ Approximation algorithms for scheduling with reservations ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ Priority algorithms for the subset-sum problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation schemes for the subset-sum problem: Survey and experimental analysis
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Worst-case analysis of greedy algorithms 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
• A Fast Approximation Algorithm For The Subset-Sum Problem
• Linear Time Algorithms for Knapsack Problems with Bounded Weights

This page was built for publication: An efficient fully polynomial approximation scheme for the Subset-Sum problem.