@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},
}