A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
type: Item
instance of: scholarly article
title: A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
zbMATH Open document ID: 1318.68200
author: Niv Buchbinder
author: Anupam Gupta
author: Joseph (Seffi) Naor
author: N. Bansal
published in: Algorithmica
publication date: 2014-12-02T00:00:00Z
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 90B22
zbMATH DE Number: 6375634
zbMATH Keywords: online algorithm
zbMATH Keywords: competitive analysis
zbMATH Keywords: metric matching
zbMATH Keywords: randomized algorithm
MaRDI profile type: Publication
full work available at URL: s00453-012-9676-9
OpenAlex ID: W2036268824
cites work: Searching in the plane
cites work: Q4542533
cites work: Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
cites work: The Online Transportation Problem: On the Exponential Boost of One Extra Server
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Online matching on a line
cites work: A General Approximation Technique for Constrained Forest Problems
cites work: Online Weighted Matching
cites work: The Online Transportation Problem
cites work: An optimal deterministic algorithm for online \(b\)-matching
cites work: On-line algorithms for weighted bipartite matching and stable marriages
cites work: Approximation and Online Algorithms
cites work: On the k -server conjecture
cites work: Competitive algorithms for server problems
cites work: AdWords and generalized online matching
cites work: Randomized online algorithms for minimum metric bipartite matching
cites work: Heuristic matching for graphs satisfying the triangle inequality
cites work: On a Greedy Heuristic for Complete Matching
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: The Travelling Salesman Problem and Minimum Matching in the Unit Square
DOI: 10.1007/S00453-012-9676-9
description: scientific article; zbMATH DE number 6375634