On the Advice Complexity of Online Matching on the Line

Autor:	Csaba, Béla, Nagy-György, Judit
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	We consider the matching problem on the line with advice complexity. We give a 1-competitive online algorithm with advice complexity $n-1,$ and show that there is no 1-competitive online algorithm reading less than $n-1$ bits of advice. Moreover, for each $0
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2408.11161 Zobrazit plný text záznamu View this record from Arxiv