A collection of lower bounds for online matching on the line
From MaRDI portal
Publication:2294680
DOI10.1007/978-3-319-77404-6_5zbMath1485.68314arXiv1712.07099OpenAlexW2964121702MaRDI QIDQ2294680
Carsten Fischer, Andreas Tönnis, Antonios Foivos Antoniadis
Publication date: 12 February 2020
Full work available at URL: https://arxiv.org/abs/1712.07099
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (7)
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 ⋮ Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm ⋮ Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship ⋮ Unnamed Item ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Competitive analysis for two variants of online metric matching problem
This page was built for publication: A collection of lower bounds for online matching on the line
