A competitive strategy for routing flow over time | Zendy

Umang Bhaskar | Zendy; Lisa Fleischer | Zendy; Elliot Anshelevich | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A competitive strategy for routing flow over time

Author(s) -

Umang Bhaskar,

Lisa Fleischer,

Elliot Anshelevich

Publication year - 2011

Publication title -

acm sigecom exchanges

Language(s) - English

Resource type - Journals

ISSN - 1551-9031

DOI - 10.1145/1998549.1998554

Subject(s) - computer science , routing (electronic design automation) , flow (mathematics) , constant (computer programming) , flow network , flow routing , static routing , work (physics) , mathematical optimization , computer network , mathematical economics , routing protocol , economics , mathematics , engineering , mechanical engineering , geometry , geotechnical engineering , programming language

Network routing games are used to understand the impact of individual users' decisions on network efficiency. Prior work on routing games uses a simplified model of network flow where all flow exists simultaneously. In our work, we examine routing games in a flow-over-time model. We show that by reducing network capacity judiciously, the network owner can ensure that the equilibrium is no worse than a small constant times the optimal in the original network, for two natural measures of optimality. These are the first upper bounds on the price of anarchy in the flow-over-time model for general networks.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research