Multiplicative auction algorithm for approximate maximum weight bipartite matching

We present an auction algorithm using multiplicative instead of constant weight updates to compute a \((1-\varepsilon )\) $(1-\epsilon )$ -approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time \(O(m\varepsilon ^{-1})\) $O(m{\epsilon }^{-1})$ , beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM ’14] that runs in \(O(m\varepsilon ^{-1}\log \varepsilon ^{-1})\) $O(m{\epsilon }^{-1}log{\epsilon }^{-1})$ . Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a \((1-\varepsilon )\) $(1-\epsilon )$ -approximate maximum weight matching under (1) one-sided vertex deletions (with incident edges) and (2) one-sided vertex insertions (with incident edges sorted by weight) to the other side. The total time time used is \(O(m\varepsilon ^{-1})\) $O(m{\epsilon }^{-1})$ , where m is the sum of the number of initially existing and inserted edges.