Tuesday, 15:15 - 15:40 h, Room: H 3013


Lisa Fleischer
Competitive strategies for routing flow over time

Coauthors: Elliot Anshelevich, Umang Bhaskar


The study of routing games is motivated by the desire to understand the impact of many individual users' decisions on network efficiency. To do this, prior work uses a simplified model of network flow where all flow exists simultaneously, and users route flow to either minimize their maximum delay or their total delay. Both of these measures are surrogates for measuring how long it takes to get all of your traffic through the network over time.
Instead of using these surrogates, we attempt a more direct study of how competition among users effects network efficiency by examining routing games in a flow-over-time model. We show that the network owner can reduce available capacity so that the competitive equilibrium in the reduced network is no worse than a small constant times the optimal solution in the original network using two natural measures of optimum: the time by which all flow reaches the destination, and the average amount of time it takes flow to reach the destination.


Talk 1 of the invited session Tue.3.H 3013
"Combinatorial optimization and equilibria for flows over time" [...]
Cluster 2
"Combinatorial optimization" [...]


  The deal is that Indiana Payday Loans online can save your time, nerves and make a solution of all your financial problems. In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.