Počet záznamů: 1  

On randomized online labeling with polynomially many labels

  1. 1.
    SYSNO ASEP0395301
    Druh ASEPC - Konferenční příspěvek (mezinárodní konf.)
    Zařazení RIVD - Článek ve sborníku
    NázevOn 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 strans. 291-302
    Poč.str.12 s.
    Forma vydáníTištěná - P
    AkceInternational Colloquium, ICALP 2013 /40./
    Datum konání08.07.2013-12.07.2013
    Místo konáníRiga
    ZeměLT - Litva
    Typ akceWRD
    Jazyk dok.eng - angličtina
    Země vyd.DE - Německo
    Klíč. slovaonline labeling ; complexity
    Vědní obor RIVBA - Obecná matematika
    CEPIAA100190902 GA AV ČR - Akademie věd
    GBP202/12/G061 GA ČR - Grantová agentura ČR
    Institucionální podporaMU-W - RVO:67985840
    UT WOS000342686600025
    EID SCOPUS84880251631
    DOI10.1007/978-3-642-39206-1_25
    AnotaceWe 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
    KontaktJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Rok sběru2014
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.