ON ONLINE LABELING WITH LARGE LABEL SET
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
ON ONLINE LABELING WITH LARGE LABEL SET
Original language description
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 > 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 > 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 >= 2(1+(log n)3) by giving a matching upper bound.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
—
Volume of the periodical
33
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
19
Pages from-to
1175-1193
UT code for WoS article
000487856600003
EID of the result in the Scopus database
2-s2.0-85071485475