Invited Session Mon.3.MA 004

Monday, 15:15 - 16:45 h, Room: MA 004

Cluster 20: Robust optimization [...]

Robust network optimization


Chair: Ebrahim Nasrabadi and Sebastian Stiller



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

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.



Monday, 15:45 - 16:10 h, Room: MA 004, Talk 2

David Adjiashvili
Fault-tolerant shortest paths - Beyond the uniform failure model


The overwhelming majority of survivable (fault-tolerant) network design models assume a uniform scenario set. Such a scenario set assumes that every subset of the network resources (edges or vertices) of a given cardinality k comprises a scenario. While this approach yields problems with clean combinatorial structure and good algorithms, it often fails to capture the true nature of robustness coming from applications.
One natural refinement of the uniform model is obtained by partitioning the set of resources into faulty and secure resources. The scenario set contains every subset of at most k faulty resources. This work studies the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest Path problem in this failure model. We present complexity results alongside exact and approximation algorithms for FTP. We emphasize the vast increase in the complexity of the problem with respect to its uniform analogue, the Edge-Disjoint Paths problem.


  cash advance loans . But at the same time, it acts only with sexual arousal. Buy Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.