---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Da Wei
foaf_name: Zheng, Da Wei
foaf_surname: Zheng
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
bibo_doi: 10.1007/978-3-031-32726-1_32
bibo_volume: 13904
dct_date: 2023^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0302-9743
- http://id.crossref.org/issn/1611-3349
- http://id.crossref.org/issn/9783031327254
dct_language: eng
dct_publisher: Springer Nature@
dct_title: Multiplicative auction algorithm for approximate maximum weight bipartite
matching@
...