2023/01/22 by Da Wei Zheng, Monika Henzinger, Zheng, Da Wei +1
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2301.09217
openalex publication_date 2023/01/22 · openalex created_date 2023/01/25 · openalex updated_date 2026/07/30
\newcommand\epsε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), beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM '14] that runs in O(m\eps-1log \eps-1). 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) 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 used is O(m\eps-1), where m is the sum of the number of initially existing and inserted edges.