## 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**

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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.