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...

Full description

Saved in:
Bibliographic Details
Published in:SIGecom exchanges 2015-01, Vol.13 (2), p.36-40
Main Authors: Bhaskar, Umang, Ligett, Katrina
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1551-9031
1551-9031
DOI:10.1145/2728732.2728737