A selfish routing based network improvement problem |
| |
Authors: | Binwu Zhang Shu-Cherng Fang |
| |
Institution: | 1.Department of Mathematics and Physics,Hohai University,Changzhou,China;2.Department of Industrial and Systems Engineering,North Carolina State University,Raleigh,USA;3.Mathematical Sciences and Industrial Engineering,Tsinghua University,Beijing,China |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|