Network expansion by adding arcs and/or nodes

CSpace > 系统科学研究所

	Network expansion by adding arcs and/or nodes
	Yang, XG; Zhang, JZ
	2005-03-01
发表期刊	PROGRESS IN NATURAL SCIENCE
ISSN	1002-0071
卷号	15 期号:3 页码:200-204
摘要	In this paper, we consider a new network improvement model, which is to expand a network by adding new arcs and/ or new nodes to satisfy the excess demand. For the new arcs and new nodes, there are constructing costs for building these new facilities. The purpose of our model is to minimize the total constructing cost. It is found that even if the constructing costs for all new nodes are zero or all new arcs are zero, solving the problem within an approximation ratio 0 (In(V-1 (+ V)()) remains NP-hard, where V)(2)(1) (is the original node set, and V)(2) is the candidate node set. We also present an MIP formulation for the problem and propose some heuristic ideas to solve the problem.
关键词	network expansion arc/node inapproximability MIP formulation
语种	英语
WOS研究方向	Materials Science ; Science & Technology - Other Topics
WOS类目	Materials Science, Multidisciplinary ; Multidisciplinary Sciences
WOS记录号	WOS:000229158600002
出版者	TAYLOR & FRANCIS LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/1492
专题	系统科学研究所
通讯作者	Yang, XG
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China 2.City Univ Hong Kong, Kowloon, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Yang, XG,Zhang, JZ. Network expansion by adding arcs and/or nodes[J]. PROGRESS IN NATURAL SCIENCE,2005,15(3):200-204.
APA	Yang, XG,&Zhang, JZ.(2005).Network expansion by adding arcs and/or nodes.PROGRESS IN NATURAL SCIENCE,15(3),200-204.
MLA	Yang, XG,et al."Network expansion by adding arcs and/or nodes".PROGRESS IN NATURAL SCIENCE 15.3(2005):200-204.