Minimal on-line labelling

The problem of on-line labelling is one of assigning integer labels in the range 1 to N to an input stream of at most N distinct items, drawn from a linearly ordered set, so that at each step the labels respect the ordering on the items. To maintain this constraint, items may have to be relabelled to accommodate new ones. With T(M,N) denoting the total number of relabellings that have to be performed for the first M inputs, it is known that for any given constant c in the range 0<c<1 there are exact bounds T(Nc,N)=Θ(NlogN) and T(cN,N)=Θ(Nlog²N). However, in the case c=1, when the labelling is called minimal, is known only that T(N,N)=O(Nlog³N). Existing algorithms for minimal on-line labelling are complicated, and our aim in this paper is to give a simplified and self-contained account of the problem.