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

doi:10.1007/s10898-017-0514-0

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 计算数学与科学工程计算研究所

	A new fully polynomial time approximation scheme for the interval subset sum problem
	Diao, Rui; Liu, Ya-Feng; Dai, Yu-Hong
刊名	JOURNAL OF GLOBAL OPTIMIZATION
	2017-08-01
卷号	68 期号:4 页码:749-775
关键词	Interval subset sum problem Computational complexity Solution structure Fully polynomial time approximation scheme Worst-case performance
ISSN号	0925-5001
DOI	10.1007/s10898-017-0514-0
英文摘要	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.
资助项目	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
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000405722900004
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/26141]
专题	计算数学与科学工程计算研究所
通讯作者	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.