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

Hochbaum, Dorit S.; Shmoys, David B.

Math. Oper. Res. 10, 180-184 (1985).

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.

MSC:

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

Keywords:

best possible heuristic; complete graph; location on networks; 2- approximation algorithm; k-center problem; triangle inequality; strong stable set; NP-completeness