An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
DOI10.1007/978-3-540-75520-3_47zbMATH Open1151.68742OpenAlexW1525987715MaRDI QIDQ3527240FDOQ3527240
N. 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) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (15)
- Stochastic Online Metric Matching
- An 0(n log n) algorithm for the convex bipartite matching problem
- Deterministic primal-dual algorithms for online \(k\)-way matching with delays
- Permutation Strikes Back: The Power of Recourse in Online Metric Matching
- An \(O(\log n)\)-competitive posted-price algorithm for online matching on the line
- Online facility assignment for general layout of servers on a line
- Title not available (Why is that?)
- Dynamic Stochastic Matching Under Limited Time
- Competitive analysis for two variants of online metric matching problem
- Capacity-insensitive algorithms for online facility assignment problems on a line
- A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
- Deterministic primal-dual algorithms for online \(k\)-way matching with delays
- A near-linear time ε-approximation algorithm for geometric bipartite matching
- An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3527240)
