BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20250309T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69cf6a725a11c
DTSTART;TZID=America/Toronto:20250529T130000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20250529T143000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/co-reading-g
 roup-david-aleman-3
SUMMARY:C&O Reading Group -David Aleman
CLASS:PUBLIC
DESCRIPTION:TITLE:Unsplittable Multicommodity Flows in Outerplanar Graphs\n
 \nSPEAKER:\n David Aleman\n\nAFFILIATION:\n University of Waterloo\n\nLOCA
 TION:\n MC 6029\n\nABSTRACT:\n\nGiven a graph G with edge capacities and m
 ultiple source-sink pairs\,\neach with an associated demand\, the multicom
 modity flow problem\nconsists of routing all demands simultaneously withou
 t violating edge\ncapacities. The graph obtained by including an edge (s_i
 \,t_i) for a\ndemand with source-sink s_i\,t_i is called the demand graph 
 H.\n\nA multicommodity flow is called unsplittable if all the flow between
  a\nsource-sink pair is routed along a single path. In general\, existence
 \nof a feasible (fractional) flow does not imply the existence of an\nunsp
 littable flow\, even in very simple settings.  This leads to a\nnatural q
 uestion: given a feasible flow\, does there exist an\nunsplittable flow wh
 ich satisfies all the demands and violates the\nedge capacities (in an add
 itive sense) by at most a small factor times\nthe value of the maximum dem
 and Dmax? \n\nDinitz\, Garg and Goemans proved that in the single-source 
 setting\n(i.e.\, when H is a star)\, any feasible fractional flow can be\n
 converted into an unsplittable flow that violates the edge capacities\nby 
 no more than Dmax. \n\nThe problem is significantly less understood when 
 the demand graph H\nis arbitrary. Schrijver\, Seymour and Winkler proved 
 that if G is a\ncycle\, then any feasible multicommodity flow can be conve
 rted into an\nunsplittable one that violates the edge capacities by at mos
 t 3Dmax/2.\nBefore our work\, cycles were the only known nontrivial class 
 of graphs\nfor which an unsplittable flow was guaranteed to exist\, incurr
 ing at\nmost an additive O(Dmax) violation of edge capacities\, whenever a
 \nfeasible flow existed. In this talk\, I will discuss how to extend this\
 nresult to the class of outerplanar graphs.\n\nThis is a joint work with N
 ikhil Kumar.
DTSTAMP:20260403T072122Z
END:VEVENT
END:VCALENDAR