Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching

$\newcommand{\eps}{\varepsilon}$ We present an auction algorithm using multiplicative instead of constant weight updates to compute a $(1-\eps)$-approximate maximum weight matching (MWM) in a bipartite graph with $n$ vertices and $m$ edges in time $O(m\eps^{-1}\log(\eps^{-1}))$, matching the running time of the linear-time approximation algorithm of Duan and Pettie [JACM '14]. Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a $(1-\eps)$-approximate maximum weight matching under (1) edge deletions in amortized $O(\eps^{-1}\log(\eps^{-1}))$ time and (2) one-sided vertex insertions. If all edges incident to an inserted vertex are given in sorted weight the amortized time is $O(\eps^{-1}\log(\eps^{-1}))$ per inserted edge. If the inserted incident edges are not sorted, the amortized time per inserted edge increases by an additive term of $O(\log n)$. The fastest prior dynamic $(1-\eps)$-approximate algorithm in weighted graphs took time $O(\sqrt{m}\eps^{-1}\log (w_{max}))$ per updated edge, where the edge weights lie in the range $[1,w_{max}]$.