ON ONLINE LABELING WITH LARGE LABEL SET

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404560" target="_blank" >RIV/00216208:11320/19:10404560 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mHE4CuXDtX" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mHE4CuXDtX</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/17M1117458" target="_blank" >10.1137/17M1117458</a>

Jazyk výsledku

angličtina

Název v původním jazyce

ON ONLINE LABELING WITH LARGE LABEL SET

Popis výsledku v původním jazyce

In the online labeling problem with parameters n and m we are presented with a sequence of n items from a totally ordered universe U and must assign each arriving item a label from the label set {1, ..., m} so that the order of labels respects the order on U. As new items arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items are maintained in sorted order in an array of length m, and we pay unit cost for moving an item. For the case m = en for constant c &gt; 1, an algorithm of Itai, Konheim, and Rodeh (1981) achieves total cost O(m(logn)(2)), which is asymptotically optimal (Bulanek, Koucky, and Saks (2015)). For the case of m = Theta(n(l +C)) for constant C &gt; 0, algorithms are known that use 0(n logn) relabelings. A matching lower bound was provided in Dietz, Seiferas, and Zhang (2005). The lower bound proof had two parts: a lower bound for a problem called prefix bucketing and a reduction from prefix bucketing to online labeling. We present a simplified version of their reduction, together with a full proof (which was not given in Dietz, Seiferas, and Zhang (2004)). We also simplify and improve the analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to larger m. Our lower bound for m from n(1+C) to 2(n) is Omega((nlogn)/(log log m - log log n)). This reduces to the asymptotically optimal bound Omega(nlogn) when m = Theta(n(l+C)). We show that our bound is asymptotically optimal for the case of m &gt;= 2(1+(log n)3) by giving a matching upper bound.

Název v anglickém jazyce

ON ONLINE LABELING WITH LARGE LABEL SET

Popis výsledku anglicky

In the online labeling problem with parameters n and m we are presented with a sequence of n items from a totally ordered universe U and must assign each arriving item a label from the label set {1, ..., m} so that the order of labels respects the order on U. As new items arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items are maintained in sorted order in an array of length m, and we pay unit cost for moving an item. For the case m = en for constant c &gt; 1, an algorithm of Itai, Konheim, and Rodeh (1981) achieves total cost O(m(logn)(2)), which is asymptotically optimal (Bulanek, Koucky, and Saks (2015)). For the case of m = Theta(n(l +C)) for constant C &gt; 0, algorithms are known that use 0(n logn) relabelings. A matching lower bound was provided in Dietz, Seiferas, and Zhang (2005). The lower bound proof had two parts: a lower bound for a problem called prefix bucketing and a reduction from prefix bucketing to online labeling. We present a simplified version of their reduction, together with a full proof (which was not given in Dietz, Seiferas, and Zhang (2004)). We also simplify and improve the analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to larger m. Our lower bound for m from n(1+C) to 2(n) is Omega((nlogn)/(log log m - log log n)). This reduces to the asymptotically optimal bound Omega(nlogn) when m = Theta(n(l+C)). We show that our bound is asymptotically optimal for the case of m &gt;= 2(1+(log n)3) by giving a matching upper bound.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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)

Rok uplatnění

2019

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 periodika

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Svazek periodika

33

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

1175-1193

Kód UT WoS článku

000487856600003

EID výsledku v databázi Scopus

2-s2.0-85071485475