TY - JOUR

T1 - On online labeling with large label Set

AU - Babka, Martin

AU - Bulanek, Jan

AU - Cun, Vladimr

AU - Koucky, Michal

AU - Saks, Michael E.

N1 - Funding Information:
\ast Received by the editors February 21, 2017; accepted for publication (in revised form) April 2, 2019; published electronically July 2, 2019. A preliminary version of this paper appeared in the Proceedings of the 2012 European Symposium on Algorithms [1]. https://doi.org/10.1137/17M1117458 Funding: The work of the first and third authors was supported by the Czech Science Foundation under grant GA14-10799S. The work of the fourth author was supported in part by the Center of Excellence CE-ITI (P202/12/G061 of GACR).\v The work of the fifth author was supported in part by the NSF under grants CCF-0832787 and CCF-1218711. \dagger Department of Theoretical Computer Science and Mathematical Logic, Charles University, 118 00 Prague, Czech Republic (babkys@gmail.com, vcunat@gmail.com). \ddagger Institute of Mathematics, Academy of Sciences CR, 115 67 Prague, Czech Republic (jan.bulanek@ gmail.com). \S Computer Science Institute, Charles University, 118 00 Prague, Czech Republic (koucky@iuuk. mff.cuni.cz). \P Department of Mathematics, Hill Center, Rutgers University, Piscataway, NJ 08854-8019 (saks@ math.rutgers.edu).
Publisher Copyright:
© 2019 Society for Industrial and Applied Mathematics

PY - 2019

Y1 - 2019

N2 - 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 = cn for constant c > 1, an algorithm of Itai, Konheim, and Rodeh (1981) achieves total cost O(n(log n)2), which is asymptotically optimal (Bul\'anek, Kouck\' y, and Saks (2015)). For the case of m = \Theta (n1+C) for constant C > 0, algorithms are known that use O(n log n) 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 n1+C to 2n is \Omega ((n log n)/(log log m - log log n)). This reduces to the asymptotically optimal bound \Omega (n log n) when m = \Theta (n1+C). We show that our bound is asymptotically optimal for the case of m \geq 21+(log n)3 by giving a matching upper bound.

AB - 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 = cn for constant c > 1, an algorithm of Itai, Konheim, and Rodeh (1981) achieves total cost O(n(log n)2), which is asymptotically optimal (Bul\'anek, Kouck\' y, and Saks (2015)). For the case of m = \Theta (n1+C) for constant C > 0, algorithms are known that use O(n log n) 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 n1+C to 2n is \Omega ((n log n)/(log log m - log log n)). This reduces to the asymptotically optimal bound \Omega (n log n) when m = \Theta (n1+C). We show that our bound is asymptotically optimal for the case of m \geq 21+(log n)3 by giving a matching upper bound.

KW - Algorithms

KW - File maintenance problem

KW - Lower bounds

KW - Online labeling

UR - http://www.scopus.com/inward/record.url?scp=85071485475&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071485475&partnerID=8YFLogxK

U2 - 10.1137/17M1117458

DO - 10.1137/17M1117458

M3 - Article

AN - SCOPUS:85071485475

SN - 0895-4801

VL - 33

SP - 1175

EP - 1193

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -