Hidde Koerts, TBA
2026-03-24 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)

Tung H. Nguyen, TBA
2026-03-31 16:30 - 17:30

Mamadou Moustapha Kanté, TBA
2026-04-07 16:30 - 17:30

Xavier Goaoc, TBA
2026-05-19 16:30 - 17:30

Sarah Morell, Unsplittable Transshipments
2026-05-26 16:30 - 17:30
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.

Maria Chudnovsky, TBA
2026-06-02 16:30 - 17:30

Martin Milanič, TBA
2026-06-09 16:30 - 17:30
