A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching

DOI10.1007/s00453-012-9676-9zbMath1318.68200OpenAlexW2036268824MaRDI QIDQ476428

Anupam Gupta, Niv Buchbinder, Joseph (Seffi) Naor, Nikhil Bansal

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9676-9

zbMATH Keywords

competitive analysisrandomized algorithmonline algorithmmetric matching

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (13)

A poly-log competitive posted-price algorithm for online metrical matching on a spider ⋮ A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line ⋮ Online bottleneck semi-matching ⋮ Online minimum matching with uniform metric and random arrivals ⋮ A \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ Online bottleneck matching on a line ⋮ Online semi-matching problem with two heterogeneous sensors in a metric space ⋮ Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship ⋮ Improved bounds for randomized preemptive online matching ⋮ Unnamed Item ⋮ Deterministic min-cost matching with delays ⋮ Online facility assignment ⋮ Greedy metric minimum online matchings with random arrivals

Cites Work

• Unnamed Item
• Searching in the plane
• On-line algorithms for weighted bipartite matching and stable marriages
• An optimal deterministic algorithm for online \(b\)-matching
• Online matching on a line
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Heuristic matching for graphs satisfying the triangle inequality
• Competitive algorithms for server problems
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
• AdWords and generalized online matching
• Randomized online algorithms for minimum metric bipartite matching
• On a Greedy Heuristic for Complete Matching
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• On the k -server conjecture
• The Online Transportation Problem
• Online Weighted Matching
• A General Approximation Technique for Constrained Forest Problems
• The Online Transportation Problem: On the Exponential Boost of One Extra Server
• Approximation and Online Algorithms
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching