Morell–Skutella-type conjecture for unsplittable transshipments

From papers

Let G=(V,A)G=(V,A) be the transshipment network, let bb specify the vertex balances, and let xx be a feasible bb-transshipment. Write dmaxd_{\max} for the maximum demand, and let AA be the set of arcs. An unsplittable bb-transshipment routes each demand along a single path while satisfying the balance requirements.

Morell–Skutella-type conjecture. Given a bb-transshipment xx, one can efficiently compute an unsplittable bb-transshipment yy such that

xadmaxyaxa+dmaxfor all aA.x_a-d_{\max}\leq y_a\leq x_a+d_{\max}\qquad\text{for all }a\in A.

This extends a conjecture for single-source unsplittable flows by Morell and Skutella to transshipments. The statement asks for simultaneous additive upper and lower arc-flow guarantees; the source describes it as an open question, even in the special single-source case, and conjectures both existence and efficient computability.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Srinwanti Debgupta, Sarah Morell and Martin Skutella, “Unsplittable Transshipments”, arXiv:2602.07230 (2026).

Solutions 0

No solutions have been posted yet.