A new fully polynomial time approximation scheme for the interval subset sum problem

DOI10.1007/S10898-017-0514-0MaRDI QIDQ1675574zbMATH OpenOpenAlexFDO

Authors Rui Diao, Ya-Feng Liu, Yuhong Dai

Publication date 2 November 2017

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.06928

zbMATH Keywords

computational complexityfully polynomial time approximation schemeinterval subset sum problemsolution structureworst-case performance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: The interval subset sum problem (ISSP) is a generalization of the well-known subset sum problem. Given a set of intervals $left{[a_{i,1},a_{i,2}]ight}_{i=1}^n$ and a target integer $T,$ the ISSP is to find a set of integers, at most one from each interval, such that their sum best approximates the target $T$ but cannot exceed it. In this paper, we first study the computational complexity of the ISSP. We show that the ISSP is relatively easy to solve compared to the 0-1 Knapsack problem (KP). We also identify several subclasses of the ISSP which are polynomial time solvable (with high probability), albeit the problem is generally NP-hard. Then, we propose a new fully polynomial time approximation scheme (FPTAS) for solving the general ISSP problem. The time and space complexities of the proposed scheme are $calOleft(nmaxleft1/epsilon,lognightight)$ and $calOleft(n+1/epsilonight),$ respectively, where $epsilon$ is the relative approximation error. To the best of our knowledge, the proposed scheme has almost the same time complexity but a significantly lower space complexity compared to the best known scheme. Both the correctness and efficiency of the proposed scheme are validated by numerical simulations. In particular, the proposed scheme successfully solves ISSP instances with $n=100,000$ and $epsilon=0.1\mathrm{\%}$ within one second.

Recommendations

• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A Fast Approximation Algorithm For The Subset-Sum Problem
• scientific article; zbMATH DE number 1104339
• Approximation schemes for the subset-sum problem: Survey and experimental analysis
• A new linear storage, polynomial-time approximation scheme for the subset-sum problem

Cites work

• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Computing and Combinatorics
• 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 3639144 (Why is no real title available?)
• Improved low-density subset sum algorithms
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Recent advances in mathematical programming with semi-continuous variables and cardinality constraint
• Solving low density knapsacks
• Solving low-density subset sum problems

Cited in

(5)

• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• The interval subset sum problem
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Learning-augmented algorithms for online subset sum

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: A new fully polynomial time approximation scheme for the interval subset sum problem

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