A randomized O(^2k)-competitive algorithm for metric bipartite matching
From MaRDI portal
Publication:476428
DOI10.1007/S00453-012-9676-9zbMATH Open1318.68200OpenAlexW2036268824MaRDI QIDQ476428FDOQ476428
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
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
Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Queues and service in operations research (90B22)
Cites Work
- Searching in the plane
- On-line algorithms for weighted bipartite matching and stable marriages
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
- AdWords and generalized online matching
- Title not available (Why is that?)
- A General Approximation Technique for Constrained Forest Problems
- A tight bound on approximating arbitrary metrics by tree metrics
- Competitive algorithms for server problems
- On the k -server conjecture
- An optimal deterministic algorithm for online \(b\)-matching
- Online matching on a line
- The Online Transportation Problem
- Online Weighted Matching
- The Online Transportation Problem: On the Exponential Boost of One Extra Server
- Heuristic matching for graphs satisfying the triangle inequality
- 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
- Approximation and Online Algorithms
Cited In (24)
- A randomized algorithm for online metric b-matching
- Deterministic min-cost matching with delays
- Title not available (Why is that?)
- A randomized algorithm for the on-line weighted bipartite matching problem
- An 0(n log n) algorithm for the convex bipartite matching problem
- Online bottleneck matching
- Permutation Strikes Back: The Power of Recourse in Online Metric Matching
- Improved bounds for randomized preemptive online matching
- Online semi-matching problem with two heterogeneous sensors in a metric space
- A poly-log competitive posted-price algorithm for online metrical matching on a spider
- An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
- Randomized algorithm for MPMD on two sources
- A \(o(n)\)-competitive deterministic algorithm for online matching on a line
- Online bottleneck matching on a line
- Online request server matching
- Online minimum matching with uniform metric and random arrivals
- A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line
- Online facility assignment
- A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
- Greedy metric minimum online matchings with random arrivals
- A near-linear time ε-approximation algorithm for geometric bipartite matching
- Online bottleneck semi-matching
- Online bottleneck matching
- Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
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)
