Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design

doi:10.1007/s00453-007-9032-7

CSpace > 应用数学研究所

	Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design
	Chen, Xujin2 ; Chen, Bo 1
	2009-03-01
发表期刊	ALGORITHMICA
ISSN	0178-4617
卷号	53 期号:3 页码:263-297
摘要	Answering an open question published in Operations Research (54, 73-91, 2006) in the area of network design and logistic optimization, we present the first constant-factor approximation algorithms for the problem combining facility location and cable installation in which capacity constraints are imposed on both facilities and cables. We study the problem of designing a minimum cost network to serve client demands by opening facilities for service provision and installing cables for service shipment. Both facilities and cables have capacity constraints and incur buy-at-bulk costs. This Max SNP-hard problem arises in diverse applications and is shown in this paper to admit a combinatorial 19.84-approximation algorithm of cubic running time. This is achieved by an integration of primal-dual schema, Lagrangian relaxation, demand clustering and bi-factor approximation. Our techniques extend to several variants of this problem, which include those with unsplitable demands or requiring network connectivity, and provide constant-factor approximate algorithms in strongly polynomial time.
关键词	Facility location Network design Soft capacity Approximation algorithm Performance guarantee
DOI	10.1007/s00453-007-9032-7
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:000263681500001
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/7363
专题	应用数学研究所
通讯作者	Chen, Bo
作者单位	1.Univ Warwick, Warwick Business Sch, Coventry CV4 7AL, W Midlands, England 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Chen, Xujin,Chen, Bo. Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design[J]. ALGORITHMICA,2009,53(3):263-297.
APA	Chen, Xujin,&Chen, Bo.(2009).Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design.ALGORITHMICA,53(3),263-297.
MLA	Chen, Xujin,et al."Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design".ALGORITHMICA 53.3(2009):263-297.