On online labeling with large label Set

Martin Babka, Jan Bulanek, Vladimr Cun, Michal Koucky, Michael E. Saks

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1175-1193
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Issue number3
StatePublished - 2019

All Science Journal Classification (ASJC) codes

  • General Mathematics


  • Algorithms
  • File maintenance problem
  • Lower bounds
  • Online labeling


Dive into the research topics of 'On online labeling with large label Set'. Together they form a unique fingerprint.

Cite this