# Online bipartite matching with amortized $O(\log^2 n)$ replacements

Research paper by **Aaron Bernstein, Jacob Holm, Eva Rotenberg**

Indexed on: **19 Jul '17**Published on: **19 Jul '17**Published in: **arXiv - Computer Science - Data Structures and Algorithms**

#### 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 the shortest
augmenting path from the newly inserted vertex (denoted the SAP protocol) 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 \emph{any} replacement strategy,
almost matching the $\Omega(\log n)$ lower bound. The previous best known
strategy achieved amortized $O(\sqrt{n})$ replacements [Bosek, Leniowski,
Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better
than then trivial $O(n)$ bound was known except in special cases.
Our analysis immediately implies the same upper bound of $O(\log^2 n)$
reassignments for the capacitated assignment problem, where each vertex on the
static side of the bipartition is initialized with the capacity to serve a
number of vertices.
We also analyze the problem of minimizing the maximum server load. We show
that if the final graph has maximum server load $L$, then the SAP protocol
makes amortized $O( \min\{L \log^2 n , \sqrt{n}\log n\})$ reassignments. We
also show that this is close to tight because $\Omega(\min\{L, \sqrt{n}\})$
reassignments can be necessary.