Online matching on a line

DOI10.1016/j.tcs.2004.10.028zbMath1070.68157OpenAlexW2136300662MaRDI QIDQ1770389

Bernhard Fuchs, Winfried Hochstättler, Walter Kern

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.028

zbMATH Keywords

MatchingCompetitive analysisOnline algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Related Items (18)

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 ⋮ A tight analysis of Brown-Baker-Katseff sequences for online strip packing ⋮ Serve or skip: the power of rejection in online bottleneck matching ⋮ A \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ Online bottleneck matching on a line ⋮ Online semi-matching problem with two heterogeneous sensors in a metric space ⋮ Unnamed Item ⋮ A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Unnamed Item ⋮ Deterministic min-cost matching with delays ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Improved lower bound for online strip packing

Cites Work

• Unnamed Item
• Searching in the plane
• Shortest paths without a map
• Online algorithms. The state of the art
• On the k -server conjecture
• Approximation and Online Algorithms

This page was built for publication: Online matching on a line