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 ...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.展开更多
基金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.
