KMS Of Academy of mathematics and systems sciences, CAS
A new fully polynomial time approximation scheme for the interval subset sum problem | |
Diao, Rui; Liu, Ya-Feng; Dai, Yu-Hong | |
2017-08-01 | |
发表期刊 | JOURNAL OF GLOBAL OPTIMIZATION |
ISSN | 0925-5001 |
卷号 | 68期号:4页码:749-775 |
摘要 | The interval subset sum problem (ISSP) is a generalization of the well-known subset sum problem. Given a set of intervals {[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 O (n max {1/epsilon, log n} and O (n+1/epsilon), 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% within 1 s. |
关键词 | Interval subset sum problem Computational complexity Solution structure Fully polynomial time approximation scheme Worst-case performance |
DOI | 10.1007/s10898-017-0514-0 |
语种 | 英语 |
资助项目 | NSFC[11671419] ; NSFC[11331012] ; NSFC[11631013] ; NSFC[11571221] ; NSFC[71331001] ; Key Project of Chinese National Programs for Fundamental Research and Development[2015CB856000] |
WOS研究方向 | Operations Research & Management Science ; Mathematics |
WOS类目 | Operations Research & Management Science ; Mathematics, Applied |
WOS记录号 | WOS:000405722900004 |
出版者 | SPRINGER |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/26142 |
专题 | 计算数学与科学工程计算研究所 |
通讯作者 | Liu, Ya-Feng |
作者单位 | Chinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci & Engn Comp, Beijing 100190, Peoples R China |
推荐引用方式 GB/T 7714 | Diao, Rui,Liu, Ya-Feng,Dai, Yu-Hong. A new fully polynomial time approximation scheme for the interval subset sum problem[J]. JOURNAL OF GLOBAL OPTIMIZATION,2017,68(4):749-775. |
APA | Diao, Rui,Liu, Ya-Feng,&Dai, Yu-Hong.(2017).A new fully polynomial time approximation scheme for the interval subset sum problem.JOURNAL OF GLOBAL OPTIMIZATION,68(4),749-775. |
MLA | Diao, Rui,et al."A new fully polynomial time approximation scheme for the interval subset sum problem".JOURNAL OF GLOBAL OPTIMIZATION 68.4(2017):749-775. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论