Seminar by Umang Bhaskar
Network improvement for equilibrium routing
Umang Bhaskar
California Institute of Technology, USA
Date: Monday, November 25th, 2013
Time: 11:30 AM
Venue: CS102.Abstract:
In many diverse applications, users strategically choose routes in a network to minimize the delay they face. Examples of such applications are road traffic, data networks, and cloud computing marketplaces. Routing games model this strategic behaviour of the users, and are used to understand and predict the impact of this behaviour on the traffic and delays in the network.
We consider a fundamental problem facing the manager of such a network: to make improvements to the network under a fixed budget, so that the average delay for the strategic users is minimized. The problem is modeled using routing games and widely studied in transportation research. However, despite its practical relevance, there are no proven guarantees for polynomial-time algorithms. In this talk, I will present both algorithms and hardness results for network improvement in a number of different network topologies, and describe a number of related problems as directions for future research.
This is joint work with Katrina Ligett and Leonard Schulman.
About the speaker:
Umang Bhaskar after a PhD from Dartmouth College is a post-doctoral researcher in the Center for Mathmatics and Information at Caltech. His BTech is from NIT, Allahabad and MTech from IIT Bombay. He is research interests are algorithmic game theory, approximation algorithms and online algorithms.