Recent Progress in Bipartite Matching Problems

In this talk, I will survey two recent results in the minimum weight bipartite matching problem in planar and minor free
graphs. The first result is by Asathulla, Khanna, Lahn, and Raghvendra in SODA 2018. The paper gave an $\tilde{O}(n^{4/3} \log C)$ algorithm for minimum cost bipartite perfect matching. The result was later improved to $\tilde{O}(n^{6/5}) \log nC$ by Lahn and Raghvendra. Both results are based on the cost scaling paradigm of Gabow and Tarjan, and uses efficient augmenting path finding data structures based planar r-divisions. The previous best result is $\tilde{O}(n^{3/2})$ based on planar separators.