Monday, 15:15 - 15:40 h, Room: MA 004


Sebastian Stiller
Robust network flows

Coauthors: Dimitris Bertsimas, Telha Claudio, Kai-Simon Goetzmann, Ebrahim Nasrabadi


This talk collects results on four different variants of robust network flows: the cost-robust counterpart, the strict robust counterpart, and the adjustable robust counterpart of the maximum network flow problem, and the robust flow-over-time problem. For all four models we consider scenario sets where at most a fixed number of coefficients in the input can change and all coefficients are limited within given intervals.
The results on the cost-robust counterpart are derived in the form of a general result on cost-robust integer programs, in particular for those with TUM matrices.
The strict robust network flow is shown to be polynomial time solvable but far too conservative.
The (fractional) adjustable robust flow problem is shown to be NP-hard. It lacks a lot of the properties of nominal network flows. Nevertheless, it exhibits a variant of the min-cut-max-flow property, which we proof via a game theoretic argument. We also describe some efficiently solvable special cases.
The robust flow-over-time is already hard on series-parallel graphs and in general cannot be solved by a temporally repeated flow.


Talk 1 of the invited session Mon.3.MA 004
"Robust network optimization" [...]
Cluster 20
"Robust optimization" [...]


  The main criterion for them is your ability to repay any Wisconsin Loans Online, they are not interested in your previous attempts, the current one is all that matters. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.