Network expansion by adding arcs and/or nodes  

作　　者：YANGXiaoguang ZHANGJianzhong 

机构地区：[1]AcademyofMathematicsandSystemsScience,ChineseAcademyofSciences,Beijing100080,China [2]CityUniversityofHongKong,Kowloon,HongKong,China

出　　处：《Progress in Natural Science:Materials International》2005年第3期200-204,共5页自然科学进展·国际材料（英文版）

基　　金：theHongKongUniversitiesGrantCouncil(GrantNos .CERGCITYU 10 81/ 99PandCITYU 115 3 / 0 1P) ,theNationalKeyResearchandDevelopmentProgramofChina(GrantNo .2 0 0 2CB3 12 0 0 4) ,andNationalNaturalScienceFoundationofChina (GrantNos .70 0 2 2 10 0 1,70 42 5 0

摘　　要：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.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 O(ln(|V 1 |+|V 2 |))remains NP-hard,where V 1 is the orig-inal 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 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]