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.

MSC:

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