| Network expansion by adding arcs and/or nodes |
| |
| 作者姓名： | YANG Xiaoguang ZHANG Jianzhong |
| |
| 作者单位： | Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China,City University of Hong Kong, Kowloon, Hong Kong, China |
| |
| 基金项目： | the Hong Kong Universities Grant Council，the National Key Research and Development Program of China，国家自然科学基金 |
| |
| 摘 要： | 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(|V1|+|V2|)) remains NP-hard, where V1 is the original node set, and V2 is thecandidate 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 |
Network expansion by adding arcs and/or nodes |
| |
| YANG Xiaoguang,ZHANG Jianzhong.Network expansion by adding arcs and/or nodes[J].Progress in Natural Science,2005,15(3):200-204. |
| |
| Authors: | YANG Xiaoguang ZHANG Jianzhong |
| |
| Institution: | 1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China
2. City University of Hong Kong, Kowloon, Hong Kong, China |
| |
| Abstract: | 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(|V1| |V2|)) remains NP-hard, where V1 is the original node set, and V2 is thecandidate node set. We also present an MIP formulation for the problem and propose some heuristic ideas to solve the problem. |
| |
| Keywords: | network expansion arc/node inapproximability MIP formulation |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 |
