On Online Labeling with Polynomially Many Labels

In the online labeling problem with parameters n and m the authors are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from the label set {1, 2,...,m} so that the order of labels (strictly) respects the ordering on U. As new keys 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.