Dutch Day on Optimization 2024

Single-Source Unsplittable Flows

Laura Vargas Koch, University of Bonn

The single-source unsplittable flow problem asks to send flow in a digraph with capacities from a common source to different terminals with unrelated demands, each terminal being served through a single path. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a very natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. Moreover, Morell and Skutella conjecture a version with lower and upper bounds on the flow along every arc. In this talk we will see that these conjectures are known to have many interesting connections to scheduling problems and discrepancy problems. Moreover, we will show that the conjecture by Morell and Skutella as well as a slightly weaker version of the Goemans' conjecture hold on planar graphs. 

Based on joint work with Vera Traub and Rico Zenklusen.

(back)