Paper Info
Title
A New Fully Polynomial Time Approximation Scheme for the Interval Subset Sum Problem.
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}]\\right\\} _{i=1}^n$$[ai,1,ai,2]i=1n 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. 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 for solving the general ISSP problem. The time and space complexities of the proposed scheme are $${{\\mathcal {O}}}\\left( n \\max \\left\\{ 1 / \\epsilon ,\\log n\\right\\} \\right) $$Onmax1/∈,logn and $$\\mathcal{O}\\left( n+1/\\epsilon \\right) ,$$On+1/∈, 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$$n=100,000 and $$\\epsilon =0.1\\%$$∈=0.1% within 1 s.
Year
DOI
Venue
2017
10.1007/s10898-017-0514-0
J. Global Optimization
Keywords
DocType
Volume
Interval subset sum problem,Computational complexity,Solution structure,Fully polynomial time approximation scheme,Worst-case performance,90C59,68Q25
Journal
abs/1704.06928
Issue
ISSN
Citations 
4
0925-5001
1
PageRank 
References 
Authors
0.38
10
3
Name
Order
Citations
PageRank
Rui Diao110.38
Y. F. Liu245430.59
Yu-Hong Dai3107978.67