TY - CONF
AB - 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.
AU - Zheng, Da Wei
AU - Henzinger, Monika H
ID - 13236
SN - 0302-9743
T2 - International Conference on Integer Programming and Combinatorial Optimization
TI - Multiplicative auction algorithm for approximate maximum weight bipartite matching
VL - 13904
ER -