The complexity analysis of the inverse center location problem

CSpace

	The complexity analysis of the inverse center location problem
	Cai, MC ; Yang, XG ; Zhang, JZ
	1999-09-01
发表期刊	JOURNAL OF GLOBAL OPTIMIZATION
ISSN	0925-5001
卷号	15 期号:2 页码:213-218
摘要	Given a feasible solution, the inverse optimization problem is to modify some parameters of the original problem as little as possible, and sometimes also with bound restrictions on these adjustments, to make the feasible solution become an optimal solution under the new parameter values. So far it is unknown that for a problem which is solvable in polynomial time, whether its inverse problem is also solvable in polynomial time. In this note we answer this question by considering the inverse center location problem and show that even though the original problem is polynomially solvable, its inverse problem is NP-hard.
关键词	complexity location problem networks and graphs satisfiability problem
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000082507500007
出版者	KLUWER ACADEMIC PUBL
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/14535
专题	中国科学院数学与系统科学研究院
通讯作者	Cai, MC
作者单位	1.Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China 2.City Univ Hong Kong, Dept Math, Hong Kong, Hong Kong
推荐引用方式 GB/T 7714	Cai, MC,Yang, XG,Zhang, JZ. The complexity analysis of the inverse center location problem[J]. JOURNAL OF GLOBAL OPTIMIZATION,1999,15(2):213-218.
APA	Cai, MC,Yang, XG,&Zhang, JZ.(1999).The complexity analysis of the inverse center location problem.JOURNAL OF GLOBAL OPTIMIZATION,15(2),213-218.
MLA	Cai, MC,et al."The complexity analysis of the inverse center location problem".JOURNAL OF GLOBAL OPTIMIZATION 15.2(1999):213-218.