Aaron Bernstein, Harvard University

Abstract

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes a shortest augmenting path from the newly inserted vertex (denoted SAP) uses at most amortized O(log^2 n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any strategy, almost matching the Ω(log n) lower bound. The previous best strategy achieved amortized O(√n) replacements [Bosek, Leniowski, Sankowski,Zych, FOCS 2014]. For SAP in particular, nothing better than the trivial O(n) bound was known except in special cases