Approximate Map Labeling is in $\Omega(n\log n)$
Frank Wagner
Institut für Informatik
Freie Universität Berlin
email: wagner@inf.fu-berlin.de
Report B 93-18
December 93
Get the report here or by anonymous ftp
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-93-18.ps.gz
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.