Abstract
Network infrastructures for transportation, communication, or energy transmission are an important backbone of our society. However, they are also prone to failure and intentional sabotage. In such cases it is desirable to quickly recover the service provided through the network. We introduce reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. An important new feature of this model, distinguishing it from existing robust network flow models, is that no flow can get lost in the network.
Our goal is to compute maximum flows under this robustness requirement. We investigate different variants depending on the number of failing links, the capacities available for rerouting, and integrality requirements. Using a suitably adapted concept of a minimum cut as an upper bound, we derive approximation algorithms for some of the harder variants of the problem and exact algorithms for important special cases.
This is joint work with Tom McCormick and Gianpaolo Oriolo.