The Online Metric Matching Problem for Doubling Metrics
From MaRDI portal
Publication:2843268
DOI10.1007/978-3-642-31594-7_36zbMath1272.90068OpenAlexW181346458MaRDI QIDQ2843268
Publication date: 12 August 2013
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31594-7_36
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (17)
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 \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm ⋮ Online bottleneck matching on a line ⋮ Online semi-matching problem with two heterogeneous sensors in a metric space ⋮ Unnamed Item ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Unnamed Item ⋮ Deterministic min-cost matching with delays ⋮ Fractal dimension and lower bounds for geometric problems ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stochastic Online Metric Matching
This page was built for publication: The Online Metric Matching Problem for Doubling Metrics