1 Search Results for "McCormick, S. Thomas"

Document

DOI: 10.4230/LIPIcs.ICALP.2017.89

Rerouting Flows When Links Fail

Authors: Jannik Matuschke, S. Thomas McCormick, and Gianpaolo Oriolo

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract

We introduce and investigate reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. Given a capacitated network, a path flow is reroutable if after failure of an arbitrary arc, we can reroute the interrupted flow from the tail of that arc to the sink, without modifying the flow that is not affected by the failure. Similar types of restoration, which are often termed "local", were previously investigated in the context of network design, such as min-cost capacity planning. In this paper, our interest is in computing maximum flows under this robustness assumption. An important new feature of our model, distinguishing it from existing max robust flow models, is that no flow can get lost in the network. We also study a tightening of reroutable flows, called strictly reroutable flows, making more restrictive assumptions on the capacities available for rerouting. For both variants, we devise a reroutable-flow equivalent of an s-t-cut and show that the corresponding max flow/min cut gap is bounded by 2. It turns out that a strictly reroutable flow of maximum value can be found using a compact LP formulation, whereas the problem of finding a maximum reroutable flow is NP-hard, even when all capacities are in {1, 2}. However, the tightening can be used to get a 2-approximation for reroutable flows. This ratio is tight in general networks, but we show that in the case of unit capacities, every reroutable flow can be transformed into a strictly reroutable flow of same value. While it is NP-hard to compute a maximal integral flow even for unit capacities, we devise a surprisingly simple combinatorial algorithm that finds a half-integral strictly reroutable flow of value 1, or certifies that no such solutions exits. Finally, we also give a hardness result for the case of multiple arc failures.

Cite as

Jannik Matuschke, S. Thomas McCormick, and Gianpaolo Oriolo. Rerouting Flows When Links Fail. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 89:1-89:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{matuschke_et_al:LIPIcs.ICALP.2017.89,
  author =	{Matuschke, Jannik and McCormick, S. Thomas and Oriolo, Gianpaolo},
  title =	{{Rerouting Flows When Links Fail}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{89:1--89:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.89},
  URN =		{urn:nbn:de:0030-drops-74466},
  doi =		{10.4230/LIPIcs.ICALP.2017.89},
  annote =	{Keywords: network flows, network interdiction, robust optimization}
}

Refine by Author
1 Matuschke, Jannik
1 McCormick, S. Thomas
1 Oriolo, Gianpaolo

Refine by Classification

Refine by Keyword
1 network flows
1 network interdiction
1 robust optimization

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "McCormick, S. Thomas"

Rerouting Flows When Links Fail

Abstract

Cite as

Thanks for your feedback!

Could not send message