Sarah Morell, Unsplittable Transshipments

We consider an arc-capacitated directed graph $D=(V,A)$, where each node $v$ is associated with a rational balance value $b(v)$. Nodes with negative balance values are referred to as sources, while those with positive balance values are called sinks. A feasible $b$-transshipment is a flow $f : A \to \mathbb{R}_{\ge 0}$ that routes the total supply of the sources to the sinks through $D$, while respecting the given arc capacity constraints and satisfying the balance requirements at each node. An unsplittable $b$-transshipment additionally requires that, for each source-sink pair, the flow sent from that source to that sink is routed along at most one directed path. Unsplittable $b$-transshipments (UT) generalize the well-studied single source unsplittable flow (SSUF) problem in which $D$ contains a single source and multiple sinks, and each demand must be routed along a single path from the common source to its destination.

Given a feasible $b$-transshipment $f$ that is not necessarily unsplittable, a natural question is whether there exists an feasible unsplittable $b$-transshipment flow $g$ that approximates $f$ in an arc-wise sense. In particular, we seek bounds on the maximum deviation $|f_a-g_a|$ over all arcs $a \in A$. For the special case of SSUFs, Dinitz, Garg, and Goemans (Combinatorica 1999) proved that there exists an unsplittable flow $g$ such that $g_a \leq f_a + d_{\max}$ for all $a \in A$, where $d_{\max}$ denotes the maximum demand value. Jointly with Martin Skutella (Mathematical Programming 2022), we studied unsplittable flows with arc-wise lower bounds and showed that there exists an unsplittable flow $g$ satisfying $g_a \ge f_a – d_{\max}$ for all $a \in A$.

In this talk, we extend this line of research by adapting the techniques of Dinitz, Garg, and Goemans to the more general setting of UTs. We show that, given any feasible $b$-transshipment $f$, there exists a feasible unsplittable $b$-transshipment $g$ such that $g_a \leq f_a + d_{\max}$ (resp. $g_a \ge f_a – d_{\max}$) for all $a \in A$.

This is joint work with Srinwanti Debgupta and Martin Skutella.