On randomized online labeling with polynomially many labels

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00395301" target="_blank" >RIV/67985840:_____/13:00395301 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-642-39206-1_25" target="_blank" >http://dx.doi.org/10.1007/978-3-642-39206-1_25</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-39206-1_25" target="_blank" >10.1007/978-3-642-39206-1_25</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On randomized online labeling with polynomially many labels

Popis výsledku v původním jazyce

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 isthe 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.

Název v anglickém jazyce

On randomized online labeling with polynomially many labels

Popis výsledku anglicky

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 isthe 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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Automata, Languages, and Programming. Part I

ISBN

978-3-642-39205-4

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

291-302

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Riga

Datum konání akce

8. 7. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—