BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260526T163000
DTEND;TZID=Asia/Seoul:20260526T173000
DTSTAMP:20260415T205058
CREATED:20260112T025344Z
LAST-MODIFIED:20260122T105556Z
UID:12084-1779813000-1779816600@dimag.ibs.re.kr
SUMMARY:Sarah Morell\, Unsplittable Transshipments
DESCRIPTION: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.  \nGiven 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$. \n 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$.  \n This is joint work with Srinwanti Debgupta and Martin Skutella.
URL:https://dimag.ibs.re.kr/event/2026-05-26/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR