arXiv Open Access 2021

An $Ω(\log n)$ Lower Bound for Online Matching on the Line

Kangning Wang

Lihat Sumber

Abstrak

For online matching with the line metric, we present a lower bound of $Ω(\log n)$ on the approximation ratio of any online (possibly randomized) algorithm. This beats the previous best lower bound of $Ω(\sqrt{\log n})$ and matches the known upper bound of $O(\log n)$.

Topik & Kata Kunci

cs.DS cs.DM

Penulis (1)

Kangning Wang

Format Sitasi

APA MLA BibTeX

Wang, K. (2021). An $Ω(\log n)$ Lower Bound for Online Matching on the Line. https://arxiv.org/abs/2105.12086

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2021
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓