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

DOI10.1007/978-3-540-75520-3_47MaRDI QIDQ3527240zbMATH OpenOpenAlexFDO

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

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

Recommendations

• A randomized O(^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

(21)

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