Network Improvement for Equilibrium Routing

Routing games are frequently used to model the behavior of traffic in large networks, such as road networks. In transportation research, the problem of adding capacity to a road network in a cost-effective manner to minimize the total delay at equilibrium is known as the Network Design Problem, and has received considerable attention. However, prior to our work, little was known about guarantees for polynomial-time algorithms for this problem. We obtain tight approximation guarantees for general and series-parallel networks, and present a number of open questions for future work.