|
A Faster Combinatorial Algorithm for Maximum Bipartite Matching| title | A Faster Combinatorial Algorithm for Maximum Bipartite Matching |
|---|
| start_date | 2024/09/25 |
|---|
| schedule | 11h |
|---|
| online | no |
|---|
| location_info | salle 3052 |
|---|
| summary | The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of Hopcroft and Karp (1973) shows that maximum bipartite matching can be solved in O(m√n) time on a graph with n vertices and m edges. For the case of very dense graphs, a fast matrix multiplication based approach gives a running time of O(n2.371). These results represented the fastest known algorithms for the problem until 2013, when Madry introduced a new approach based on continuous techniques achieving much faster runtime in sparse graphs. This line of research has culminated in a spectacular recent breakthrough due to Chen et al. (2022) that gives an m1+o(1) time algorithm for maximum bipartite matching (and more generally, for min cost flows).
This raises a natural question: are continuous techniques essential to obtaining fast algorithms for the bipartite matching problem? In this talk, I will describe a new, purely combinatorial algorithm for bipartite matching, that runs in ~O(m1/3n5/3) time, and hence outperforms both Hopcroft-Karp and the fast matrix multiplication based algorithms on moderately dense graphs. I will also briefly discuss some subsequent work that further improves this runtime. |
|---|
| responsibles | Szabó |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2024/09/12 14:38 UTC |
| |
|