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

Rui Diao (), Ya-Feng Liu () and Yu-Hong Dai ()
Additional contact information
Rui Diao: Chinese Academy of Sciences
Ya-Feng Liu: Chinese Academy of Sciences
Yu-Hong Dai: Chinese Academy of Sciences

Journal of Global Optimization, 2017, vol. 68, issue 4, No 4, 749-775

Abstract: 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$$ [ a i , 1 , a i , 2 ] 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. 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) $$ O n max 1 / ϵ , log n and $$\mathcal{O}\left( n+1/\epsilon \right) ,$$ O n + 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.

Keywords: Interval subset sum problem; Computational complexity; Solution structure; Fully polynomial time approximation scheme; Worst-case performance; 90C59; 68Q25 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0514-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:68:y:2017:i:4:d:10.1007_s10898-017-0514-0

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0514-0

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().