Monday, May 7, 2012
Technische Universität Berlin
Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Network flows are a rewarding object of research in combinatorial optimization. Algebraically, they can be described by totally unimodular matrices. Combinatorially, flows and their duals, the cuts, possess a number of properties that allow for a very natural and clean theory and for efficient combinatorial algorithms, e.g., to find a maximum network flow. Even certain models for flows over-time can be solved efficiently.
We consider the robust and adjustable robust counterparts of network flows. To summarize: here everything goes wrong that went well for nominal network flows. In both models an arbitrary arc set of fixed size in the underlying network can fail. The robust counterpart of a flow must be feasible for any such failure set. This is very conservative. The maximum adjustable robust counterpart allows for an adjustment of the flow after the failure. Here, one looks for a flow $x$ which after the failure admits the largest flow $y$ such that $y_e\leq x_e$ for every arc $e$.
The integral maximum robust flow problem and the integral minimum robust cut problem are polynomially solvable as in the nominal case. Yet, unlike the nominal case their objective values do not coincide. The adjustable robust flow is NP-hard even in the fractional case. Yet, one can define a minimum adjustable robust cut such that a MaxFlow-MinCut Theorem holds. This theorem follows from the existence of pure equilibria in certain two-player zero sum games.
These results are joint work with Dimitris Bertsimas, Kai-Simon Goetzmann, and Ebrahim Nasrabadi.
Colloquium - 16:00