Multiplicative auction algorithm for approximate maximum weight bipartite matching

• 成果类型: Article
• 署名作者: Zheng, Da Wei; Henzinger, Monika
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; Institute of Science & Technology - Austria
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02066-3
• 发表日期: 2025
• 页码: 881-894
• 关键词: assignment

摘要

We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1-epsilon)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time 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 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-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 epsilon(-1)), where m is the sum of the number of initially existing and inserted edges.