Cost-Effective Designs of Fault-Tolerant Access Networks in Communication Systems

doi:10.1002/net.20306

CSpace > 应用数学研究所

	Cost-Effective Designs of Fault-Tolerant Access Networks in Communication Systems
	Chen, Xujin2 ; Chen, Bo 1
	2009-07-01
发表期刊	NETWORKS
ISSN	0028-3045
卷号	53 期号:4 页码:382-391
摘要	This article is concerned with the design of fault-tolerant access networks for cost-effective communications-deploying network links and service providers (SPs) at a minimum cost, while ensuring error tolerance ability via the ring architecture. Given a set of service subscribers (SSs) in an access network, we are required to determine the locations and capacities of service providers, and to establish network links in terms of rings connecting SSs to SPs. We pay link costs for ring constructions and pay management costs for selecting SPs with capacities sufficient to manage the SSs in their rings. The network design aims to minimize the sum of the link costs and the management costs. Two APX-hard problems in the general network design are studied in this article to address the scalable and modular features of SP capacities. Despite the logarithmic inapproximability that we show for one problem, constant-factor approximation algorithms are proposed to solve the other problem and its variant in quartic time. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 53(4),382-391 2009
关键词	communication network design approximation algorithm primal-dual schema
DOI	10.1002/net.20306
语种	英语
资助项目	NSF[10771209]
WOS研究方向	Computer Science ; Operations Research & Management Science
WOS类目	Computer Science, Hardware & Architecture ; Operations Research & Management Science
WOS记录号	WOS:000267529700006
出版者	JOHN WILEY & SONS INC
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/8439
专题	应用数学研究所
通讯作者	Chen, Bo
作者单位	1.Univ Warwick, Warwick Business Sch, Coventry CV4 7AL, W Midlands, England 2.Chinese Acad Sci, Inst Appl Math, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Chen, Xujin,Chen, Bo. Cost-Effective Designs of Fault-Tolerant Access Networks in Communication Systems[J]. NETWORKS,2009,53(4):382-391.
APA	Chen, Xujin,&Chen, Bo.(2009).Cost-Effective Designs of Fault-Tolerant Access Networks in Communication Systems.NETWORKS,53(4),382-391.
MLA	Chen, Xujin,et al."Cost-Effective Designs of Fault-Tolerant Access Networks in Communication Systems".NETWORKS 53.4(2009):382-391.