Density Control and on-Line Labeling Problems

摘要

We extend the notion of density to individual points on a discrete distribution.We provide a linear time algorithm to find points with certain density, showing that our definition is computationally efficient. The Hot-Spot Lemma guarantees the existence of 'congestion.' This fact lets us find overall structure on density and enables density control. We will prove an Omega(n log n) lower bound for a List Labeling Problem with a polynomial number of labels, hence we will solve a problem open for over ten years. The lower bound proof is based on an adversary strategy. The adversary will always insert the new item to a 'crowded' point which can be located by maintaining structure based on the Hot-Spot Lemma. When the adversary cannot see the actual labeling, i.e., the adversary is oblivious, we are able to provide a probabilistic adversary which forces an expected Omega (n log n/log n) relabling cost. When we restrict the algorithm to be smooth, which is satisfied by all the known labeling algorithms, a simple adversary strategy which always inserts at one end will give the following lower bounds: (1) when the number of labels is a polynomial in the number of items, the lower bound is Omega(n log n). (2). When the number of labels is linear in the number of items, the lower bound is Omega(n log sq n). (3) When the number of labels is equal to the number of items, the lower bound is Omega(n log (exp 3) n).