Invited Session Tue.3.H 3013

Tuesday, 15:15 - 16:45 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Combinatorial optimization and equilibria for flows over time


Chair: Neil Olver and Jose Correa



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

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.



Tuesday, 15:45 - 16:10 h, Room: H 3013, Talk 2

Omar Larre
Existence and uniqueness of equilibria for flows over time

Coauthors: Roberto Cominetti, José Correa


Network flows that vary over time arise naturally when modeling rapidly evolving systems such as the Internet. In this paper, we continue the study of equilibria for flows over time in the single-source single-sink deterministic queuing model proposed by Koch and Skutella. We give a constructive proof for the existence and uniqueness of equilibria for the case of a piecewise constant inflow rate, through a detailed analysis of the static flows obtained as derivatives of a dynamic equilibrium.



Tuesday, 16:15 - 16:40 h, Room: H 3013, Talk 3

Ronald Koch
Continuous and discrete flows over time

Coauthors: Ebrahim Nasrabadi, Martin Skutella


Network flows over time form a fascinating area of research. They model the temporal dynamics of network flow problems occurring in a wide variety of applications. Research in this area has been pursued in two different and mainly independent directions with respect to time modeling: discrete and continuous time models.
In this talk we deploy measure theory in order to introduce a general model of network flows over time combining both discrete and continuous aspects into a single model. Here, the flow on each arc is modeled as a Borel measure on the real line (time axis) which assigns to each suitable subset a real value, interpreted as the amount of flow entering the arc over the subset. We motivate the usage of measures as a quite natural tool for modeling flow distributions over time. In particular, we show how static flow theory can be adopted to obtain corresponding results for this general flow over time model.


  The system of instant Virginia Payday Loans allows any adult U.S. citizen. In this section we give only a brief summary recommendation for admission of Canadian Levitra. Full information can be found in the instructions for receiving medications with vardenafil.