On online labeling with large label Set

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)²), which is asymptotically optimal (Bul\'anek, Kouck\' y, and Saks (2015)). For the case of m = \Theta (n^1+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 n^1+C to 2ⁿ 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 (n^1+C). We show that our bound is asymptotically optimal for the case of m \geq 2^1+(log n⁾³ by giving a matching upper bound.