Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm

DOI10.1145/3594873arXiv2012.15593WikidataQ130910631 ScholiaQ130910631MaRDI QIDQ6051993

Michele Scquizzato, Enoch Peserico

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.15593

zbMATH Keywords

competitive analysismetric matching

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• On-line algorithms for weighted bipartite matching and stable marriages
• Online matching on a line
• A collection of lower bounds for online matching on the line
• A \(o(n)\)-competitive deterministic algorithm for online matching on a line
• The Online Metric Matching Problem for Doubling Metrics
• The Online Transportation Problem
• Online Weighted Matching
• Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
• Stochastic Online Metric Matching
• Approximation and Online Algorithms
• Online Metric Algorithms with Untrusted Predictions
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching

This page was built for publication: Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm