We look forward to seeing you in person in 3401 Siebel Center or online.
Abstract:
Auction algorithms are a very simple class of algorithms for finding maximum weight matchings in bipartite graphs. If we view one side of the bipartition as goods and the other as buyers and edge weights as utilities, auction algorithms find a social welfare-maximizing allocation of goods to buyers. In this talk, I will 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/εlog(1/ε)), matching the running time of the linear-time approximation algorithm of Duan and Pettie [JACM '14]. Our algorithm is very simple and can be extended to give a dynamic data structure that maintains a (1−ε)-approximate maximum weight matching under (1) edge deletions in amortized O(1/ε log(1/ε)) time and (2) one-sided vertex insertions. If all edges incident to an inserted vertex are given in sorted weight the amortized time is O(1/εlog(1/ε)) per inserted edge. If the inserted incident edges are not sorted, the amortized time per inserted edge increases by an additive term of O(logn).
Joint work with Monika Henzinger. IPCO '23. https://arxiv.org/abs/2301.09217
