Approximate Map Labeling is in $\Omega(n\log n)$

Frank Wagner Institut für Informatik Freie Universität Berlin email: Report B 93-18 December 93

Get the report here or by anonymous ftp 
File:   pub/reports/
Given $n$ real numbers, the $\epsilon$-CLOSENESS problem consists in deciding whether any two of them are within $\epsilon$ of each other, where $\epsilon$ is a fixed parameter of the problem. This is a basic problems with an $\Omega(n\log n)$ lower bound on the running time in the algebraic computation tree model.\\ In this paper we show that for a natural approximation version thereof the same lower bound holds. The main tool used is a lower bound theorem of Ben-Or. We introduce a new interpolation method relating the approximation version of the problem to two corresponding exact versions.\\ Using this result, we are able to prove the optimality of the running time of a cartographic algorithm, that determines an approximate solution to the so-called MAP LABELING problem. MAP LABELING was shown to be \NP -complete. The approximation algorithm discussed here is of provably optimal approximation quality.\\ Our result is the first $n \log n$ lower bound for an {\em approximate} problem. The proof method is general enough to be potentially helpful for further results of this type.