An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
From MaRDI portal
Publication:3527240
DOI10.1007/978-3-540-75520-3_47zbMath1151.68742OpenAlexW1525987715MaRDI QIDQ3527240
Nikhil Bansal, Anupam Gupta, Joseph (Seffi) Naor, Niv Buchbinder
Publication date: 25 September 2008
Published in: Algorithms – ESA 2007 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-75520-3_47
Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20)
Related Items (6)
An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Dynamic Stochastic Matching Under Limited Time ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Stochastic Online Metric Matching ⋮ Competitive strategies for an online generalized assignment problem with a service consecution constraint
This page was built for publication: An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
