Tootfinder

Unsplittable Transshipments
Srinwanti Debgupta, Sarah Morell, Martin Skutella
https://arxiv.org/abs/2602.07230 https://arxiv.org/pdf/2602.07230 https://arxiv.org/html/2602.07230
arXiv:2602.07230v1 Announce Type: new
Abstract: We introduce the Unsplittable Transshipment Problem in directed graphs with multiple sources and sinks. An unsplittable transshipment routes given supplies and demands using at most one path for each source-sink pair. Although they are a natural generalization of single source unsplittable flows, unsplittable transshipments raise interesting new challenges and require novel algorithmic techniques. As our main contribution, we give a nontrivial generalization of a seminal result of Dinitz, Garg, and Goemans (1999) by showing how to efficiently turn a given transshipment $x$ into an unsplittable transshipment $y$ with $y_a<x_a d_{\max}$ for all arcs $a$, where $d_{\max}$ is the maximum demand (or supply) value. Further results include bounds on the number of rounds required to satisfy all demands, where each round consists of an unsplittable transshipment that routes a subset of the demands while respecting arc capacity constraints.
toXiv_bot_toot