BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Unsplittable Flows in Planar Graphs [Oberseminar Discrete Optimiza
 tion]
DTSTART:20250901T161500Z
DTEND:20250901T171500Z
DTSTAMP:20260421T232300Z
UID:indico-event-593@math-events.uni-bonn.de
DESCRIPTION:Speakers: David Aleman Espinosa (University of Waterloo\, Cana
 da)\n\nGiven an undirected graph G=(V\, E(G)) with edge capacities and mul
 tiple demand pairs {(s_i\, t_i)} with associated demands {d_i}\, the multi
 commodity flow problem asks for a simultaneous routing of all demands whil
 e respecting the edge capacities. The auxiliary demand graph \nH=(V\, E(H)
 ) comprises an edge (s_i\, t_i) for each demand pair. A multicommodity flo
 w is called unsplittable if\, for every demand pair\, all the flow between
  its endpoints is routed along a single path.Already in simple settings\, 
 such as the single-source setting (H a star)\, the existence of a feasible
  fractional flow does not imply the existence of an unsplittable flow. Thi
 s leads to a natural question: given a feasible flow\, does there exist an
  unsplittable flow that satisfies all the demands while violating the edge
  capacities up to a small additive term? A seminal result of Dinitz\, Garg
 \, and Goemans is that in the single-source setting\, any feasible fractio
 nal flow can be converted into an unsplittable flow that violates the edge
  capacities by at most the maximum demand. The problem is significantly le
 ss understood outside of the single-source setting. In this talk\, we cons
 ider two natural settings arising from planar graphs: 1) Outerplanar insta
 nces\, where G is outerplanar and H is arbitrary. We show that any feasibl
 e flow can be converted into an unsplittable flow that violates edge capac
 ities by at most a constant times the maximum demand\, for some constant s
 maller than 4. This extends a classical result of Schrijver\, Seymour\, an
 d Winkler on instances with G a cycle\, where they achieved a violation of
  at most three halves of the maximum demand. Joint work with Nikhil Kumar.
 2) Fully planar instances\, where G and H are such that G + H = (V\, E(G) 
 ∪ E(H) ) is planar. We achieve a violation of at most twice the maximum 
 demand\, and show that this bound is essentially tight. Joint work with Ni
 khil Kumar\, Joseph Poremba\, and Bruce Shepherd. \n \nThe Oberseminar ta
 kes place in the conference room\, 2nd floor. Participants are invited to 
 have coffee or tea in the lounge before.\n \n\nhttps://math-events.uni-bo
 nn.de/event/593/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/593/
END:VEVENT
END:VCALENDAR