Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length

Presenter: Vijay Vazirani – Distinguished Professor, UC Irvine

Abstract:It is well-known that the proof of some prominent results in mathematics took a very long time — decades and even centuries. 

The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed — over four decades after the publication of the algorithm in 1980. MV is still the most efficient known algorithm for the problem. 

In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max flow. 

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this talk is to rectify that shortcoming. The talk is based on this paper.

Bio: Vijay Vazirani is Distinguished Professor at the University of California, Irvine. A description of his research appears in the citation of his 2022 INFORMS John von Neumann Theory Prize. Recently he completed a proof of the Micali-Vazirani maximum matching algorithm, over four decades after the publication of the algorithm itself. His most recent book (co-edited), Online and Matching-Based Market Design, appeared in July 2023.