Multiplicative auction algorithm for approximate maximum weight bipartite matching

DOI10.1007/978-3-031-32726-1_32zbMath1528.91042arXiv2301.09217OpenAlexW4377200029MaRDI QIDQ6086023

Monika R. Henzinger, Dawei Zheng

Publication date: 9 November 2023

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2301.09217

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Matching models (91B68)

Cites Work

• A nearly linear-time PTAS for explicit fractional packing and covering linear programs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Linear-Time Approximation for Maximum Weight Matching
• Algorithms for the Assignment and Transportation Problems
• A new algorithm for the assignment problem
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Multiplicative auction algorithm for approximate maximum weight bipartite matching