A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line

DOI10.1007/978-3-319-18263-6_2zbMath1421.68236OpenAlexW2225844283MaRDI QIDQ3453279

Michael Nugent, Michele Scquizzato, Antonios Foivos Antoniadis, Neal Barcelo, Kirk R. Pruhs

Publication date: 20 November 2015

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-18263-6_2

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Related Items (8)

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 ⋮ Deterministic min-cost matching with delays ⋮ Online facility assignment ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Unnamed Item ⋮ Stochastic Online Metric Matching

Cites Work

• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• On-line algorithms for weighted bipartite matching and stable marriages
• Online matching on a line
• The Online Metric Matching Problem for Doubling Metrics
• On a Greedy Heuristic for Complete Matching
• On the k -server conjecture
• The Online Transportation Problem
• Online Weighted Matching
• The Online Transportation Problem: On the Exponential Boost of One Extra Server
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line