Unsplittable Cost Flows from Unweighted Error-Bounded Variants
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.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Logic
programming
and type systems
Mathematical Dynamics and Fractals
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 512–523
- Publication date
- 1 January 2026
- Language
- EN