We model an order-maintenance problem for erasure-limited memories in terms of an online house numbering problem, where houses are added in an arbitrary fashion along a road and must be assigned labels to maintain their ordering along the road. Unlike previous order-maintenance problems, such as the file-maintenance and online list labeling problems, the optimization goal here is to minimize the maximum number of times that any house is relabeled. This goal introduces some interesting challenges, since it is “orthogonal” to that of minimizing the total time to perform a sequence of list updates. In addition to introducing this problem, we provide several algorithms for solving it, which achieve interesting tradeoffs between upper bounds on the number of maximum relabelings per element and the number of bits needed for labels.
Joint work with Jeremy T. Fineman, Michael T. Goodrich, and Tsvi Kopelowitz