Počet záznamů: 1
On randomized online labeling with polynomially many labels
- 1.
SYSNO ASEP 0395301 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název On randomized online labeling with polynomially many labels Tvůrce(i) Bulánek, Jan (MU-W) RID, SAI
Koucký, Michal (MU-W) RID, SAI, ORCID
Saks, M. (US)Zdroj.dok. Automata, Languages, and Programming. Part I. - Berlin : Springer, 2013 / Fomin F.V. ; Freivalds R. ; Kwiatkowska M. ; Peleg D. - ISBN 978-3-642-39205-4 Rozsah stran s. 291-302 Poč.str. 12 s. Forma vydání Tištěná - P Akce International Colloquium, ICALP 2013 /40./ Datum konání 08.07.2013-12.07.2013 Místo konání Riga Země LT - Litva Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova online labeling ; complexity Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd GBP202/12/G061 GA ČR - Grantová agentura ČR Institucionální podpora MU-W - RVO:67985840 UT WOS 000342686600025 EID SCOPUS 84880251631 DOI 10.1007/978-3-642-39206-1_25 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2014
Počet záznamů: 1