A best possible heuristic for the k-center problem. (English) Zbl 0565.90015

We present a 2-approximation algorithm for the k-center problem with triangle inequality. This result is ”best possible” since for any \(\delta <2\) the existence of \(\delta\)-approximation algorithm would imply that \(P=NP\). It should be noted that no \(\delta\)-approximation algorithm, for any constant \(\delta\), has been reported to date. Linear programming duality theory provides interesting insight to the problem and enables us to derive, in O(\(| E| \log | E|)\) time, a solution with value no more than twice the k-center optimal value.
A by-product of the analysis is an O(\(| E|)\) algorithm that identifies a dominating set in \(G^ 2\), the square of a graph G, the size of which is no larger than the size of the minimum dominating set in the graph G. The key combinatorial object used is called a strong stable set, and we prove the NP-completeness of the corresponding decision problem.


90B05 Inventory, storage, reservoirs
68Q25 Analysis of algorithms and problem complexity
05C35 Extremal problems in graph theory
65K05 Numerical mathematical programming methods
Full Text: DOI