On Randomized Online Labeling with Polynomially Many Labels

We prove an optimal lower bound on the complexity of

randomized

algorithms for the online labeling problem with polynomially many labels. All previous work on this problem (both upper and lower bounds) only applied to deterministic algorithms, so this is the first paper addressing the (im)possibility of faster randomized algorithms. Our lower bound Ω(

n

log(

n

)) matches the complexity of a known deterministic algorithm for this setting of parameters so it is asymptotically optimal.

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,2,…,

m

} so that the order of labels (strictly) respects the ordering 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, instead of being labeled, are maintained in sorted order in an array of length

m

, and we pay unit cost for moving an item.