Number of the records: 1
On randomized online labeling with polynomially many labels
- 1.0395301 - MÚ 2014 RIV DE eng C - Conference Paper (international conference)
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]
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : online labeling * complexity
Subject RIV: BA - General Mathematics
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.
Permanent Link: http://hdl.handle.net/11104/0223374
File Download Size Commentary Version Access Bulanek1.pdf 1 221.1 KB Publisher’s postprint require
Number of the records: 1