On randomized online labeling with polynomially many labels

0395301 - MÚ 2014 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Bulánek, Jan - Koucký, Michal - Saks, M.
On randomized online labeling with polynomially many labels.
Automata, Languages, and Programming. Part I. Berlin: Springer, 2013 - (Fomin, F.; Freivalds, R.; Kwiatkowska, M.; Peleg, D.), s. 291-302. Lecture Notes in Computer Science, 7965. ISBN 978-3-642-39205-4.
[International Colloquium, ICALP 2013 /40./. Riga (LT), 08.07.2013-12.07.2013]
Grant CEP: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: online labeling * complexity
Kód oboru RIV: BA - Obecná matematika
http://link.springer.com/chapter/10.1007%2F978-3-642-39206-1_25

We prove an optimal lower bound on the complexity of randomized algorithms for the online labeling problem with polynomially many labels. All previous work on this problem (both upper and lower bounds) only applied to deterministic algorithms, so this is the first paper addressing the (im)possibility of faster randomized algorithms. Our lower bound Ω(n log(n)) matches the complexity of a known deterministic algorithm for this setting of parameters so it is asymptotically optimal.
Trvalý link: http://hdl.handle.net/11104/0223374