BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time [Oberseminar
  Discrete Optimization]
DTSTART:20250721T081500Z
DTEND:20250721T091500Z
DTSTAMP:20260721T132000Z
UID:indico-event-564@math-events.uni-bonn.de
DESCRIPTION:Speakers: Joakim Blikstad (CWI Amsterdam)\n\nThe talk will cov
 er a recent line of combinatorial algorithm for computing exact maximum fl
 ows in directed graphs with n vertices and edge capacities O(n^2 log^26 n)
  time\, which is near-optimal in dense graphs. Our algorithm is a novel im
 plementation of the classical augmenting-path framework\; we list augmenti
 ng paths more efficiently using a new variant of the push-relabel algorith
 m that uses additional edge weights to guide the algorithm\, and we derive
  the edge weights by constructing a directed expander hierarchy.\nWhile no
 t yet efficient\, it is to our knowledge the first maximum flow algorithm 
 faster than O(m sqrt m) that has been fully implemented in code.\nThe talk
  assumes no prior knowledge in graph algorithms. It is based on the papers
 :\nMaximum Flow by Augmenting Paths in n^(2+o(1)) Time. FOCS 2024.\nCombin
 atorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs. FOCS 20
 25.\n \nJoint work with: Aaron Bernstein\, Jason Li\, Thachaphol Saranura
 k\, Ta-Wei Tu\n \n\nhttps://math-events.uni-bonn.de/event/564/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/564/
END:VEVENT
END:VCALENDAR