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

DOI10.1007/S00453-012-9676-9MaRDI QIDQ476428zbMATHOpenAlexFDO

Authors Niv Buchbinder, Anupam Gupta, Joseph (Seffi) Naor, N. 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

randomized algorithmcompetitive analysisonline algorithmmetric matching

Mathematics Subject Classification ID

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

Recommendations

• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• A robust and optimal online algorithm for minimum metric bipartite matching
• The Online Metric Matching Problem for Doubling Metrics
• A randomized algorithm for the on-line weighted bipartite matching problem
• scientific article; zbMATH DE number 7236471

Cites work

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

Cited in

(26)

• Online bottleneck matching on a line
• Online minimum matching with uniform metric and random arrivals
• A robust and optimal online algorithm for minimum metric bipartite matching
• A poly-log competitive posted-price algorithm for online metrical matching on a spider
• A randomized algorithm for online metric b-matching
• Randomized algorithm for MPMD on two sources
• Online bottleneck matching
• A near-linear time ε-approximation algorithm for geometric bipartite matching
• Online bottleneck semi-matching
• Online request server matching
• 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
• Online semi-matching problem with two heterogeneous sensors in a metric space
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• scientific article; zbMATH DE number 7758339 (Why is no real title available?)
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching
• Improved bounds for randomized preemptive online matching
• Greedy metric minimum online matchings with random arrivals
• Online bottleneck matching
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
• A randomized algorithm for the on-line weighted bipartite matching problem
• Online facility assignment

This page was built for publication: A randomized \(O(\log^2k)\)-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 Q476428)