A SELFISH ROUTING BASED NETWORK IMPROVEMENT PROBLEM  

作　　者：Binwu ZHANG Shu-Cherng FANG 

机构地区：[1]Department of Mathematics and Physics, Hohai University, Changzhou Campus, Changzhou 213022, China [2]Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27695-7906, USA Mathematical Sciences and Industrial Engineering, Tsinghua University, Beijing 100084, China

出　　处：《Journal of Systems Science & Complexity》2011年第1期68-78,共11页系统科学与复杂性学报（英文版）

基　　金：The work is supported Hohai University Funds under Grant Nos. XZX/08B002-02, 2009428211, and the US National Science Foundation under Grant No. DMI-0553310.

摘　　要：This paper considers a selfish routing based network improvement problem, in which the authors would like to find a modified latency function that results in a new Nash equilibrium flow satisfying all traffic demands subject to the target capacity, while the total modification cost on edge latency is minimized. By using the reduction from the 3-Satisfiability （3-SAT） problem to our problem, the authors show that this problem is strongly NP-hard, even for the single commodity network.

关 键 词：Nash equilibrium NP-HARD selfish routing price of anarchy. 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程] TP393[自动化与计算机技术—控制科学与工程]