An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching

DOI10.1007/978-3-540-75520-3_47MaRDI QIDQ3527240zbMATHOpenAlexFDO

Authors N. Bansal, Niv Buchbinder, Anupam Gupta, Joseph (Seffi) Naor

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• A robust and optimal online algorithm for minimum metric bipartite matching
• A randomized algorithm for the on-line weighted bipartite matching problem
• The Online Metric Matching Problem for Doubling Metrics
• scientific article; zbMATH DE number 7236471

Cited in

(19)

• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• Deterministic primal-dual algorithms for online \(k\)-way matching with delays
• Dynamic stochastic matching under limited time
• A robust and optimal online algorithm for minimum metric bipartite matching
• Competitive strategies for an online generalized assignment problem with a service consecution constraint
• A near-linear time ε-approximation algorithm for geometric bipartite matching
• scientific article; zbMATH DE number 176778 (Why is no real title available?)
• 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
• Stochastic online metric matching
• A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
• Competitive analysis for two variants of online metric matching problem
• An 0(n log n) algorithm for the convex bipartite matching problem
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching
• Capacity-insensitive algorithms for online facility assignment problems on a line
• Deterministic primal-dual algorithms for online \(k\)-way matching with delays
• Greedy metric minimum online matchings with random arrivals
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• A randomized algorithm for the on-line weighted bipartite matching problem

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)