Nearly Optimal List Labeling

Michael A. Bender, Alex Conway, Martín Farach-Colton +4

The list-labeling problem captures the basic task of storing a dynamically changing set of up to $n$ elements in sorted order in an array of size $m=(1+\Theta (1))n$. The goal is to…