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" [...]


  Today, Ohio Payday Loans are legitimate, but there are illegal transactions that are still on the rise. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis Online is the one that definitely differs from all other products.