Number of the records: 1
On randomized online labeling with polynomially many labels
- 1.
SYSNO ASEP 0395301 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title On randomized online labeling with polynomially many labels Author(s) Bulánek, Jan (MU-W) RID, SAI
Koucký, Michal (MU-W) RID, SAI, ORCID
Saks, M. (US)Source Title Automata, Languages, and Programming. Part I. - Berlin : Springer, 2013 / Fomin F.V. ; Freivalds R. ; Kwiatkowska M. ; Peleg D. - ISBN 978-3-642-39205-4 Pages s. 291-302 Number of pages 12 s. Publication form Print - P Action International Colloquium, ICALP 2013 /40./ Event date 08.07.2013-12.07.2013 VEvent location Riga Country LT - Lithuania Event type WRD Language eng - English Country DE - Germany Keywords online labeling ; complexity Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) Institutional support MU-W - RVO:67985840 UT WOS 000342686600025 EID SCOPUS 84880251631 DOI 10.1007/978-3-642-39206-1_25 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2014
Number of the records: 1