Tutte Colloquium - Richard Peng

Friday, October 7, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Title: Bipartite Matching in Almost-Linear Time and More

Speaker: Yang Peng
Affiliation: University of Waterloo
Location: MC 5501, please contact Amanda Lutz for Zoom link

Abstract:  This talk will present an algorithm that computes maximum bipartite matchings in m^{1 + o(1)} time, and discuss its connections with optimization, graph algorithms, and data structures.

The algorithmic framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. It builds the flows through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using dynamic graph data structures.