@inproceedings{13236,
abstract = {We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1−ε)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time O(mε−1log(ε−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−ε)-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ε−1log(ε−1)), where m is the sum of the number of initially existing and inserted edges.},
author = {Zheng, Da Wei and Henzinger, Monika H},
booktitle = {International Conference on Integer Programming and Combinatorial Optimization},
isbn = {9783031327254},
issn = {1611-3349},
location = {Madison, WI, United States},
pages = {453--465},
publisher = {Springer Nature},
title = {{Multiplicative auction algorithm for approximate maximum weight bipartite matching}},
doi = {10.1007/978-3-031-32726-1_32},
volume = {13904},
year = {2023},
}