Unsplittable Cost Flows from Unweighted Error-Bounded Variants

Society for Industrial and Applied Mathematics eBooks, pp. 512–523

Abstract

A famous conjecture of Goemans on single-source unsplittable flows states that one can turn any fractional flow into an unsplittable one of no higher cost, while increasing the load on any arc by at most the maximum demand. Despite extensive work on the topic, only limited progress has been made. Recently, Morell and Skutella suggested an alternative conjecture, stating that one can turn any fractional flow into an unsplittable one without changing the load on any arc by more than the maximum demand.

Authors 4

1. Chaitanya Swamy

   University of Waterloo

   Affiliation as printed

   Univ. Waterloo

2. Vera Traub

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zurich, Zurich, Switzerland

3. Laura Vargas Koch Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

4. Rico Zenklusen

   ETH Zurich

   Affiliation as printed

   Department of Mathematics, ETH Zurich, Zurich, Switzerland