A Best Possible Heuristic for the <i>k</i>-Center Problem

TLDR

No δ‑approximation algorithm for the k‑center problem has been reported to date. The paper presents a 2‑approximation algorithm for the k‑center problem under the triangle inequality. By applying linear‑programming duality, the authors design an O(|E| log |E|) algorithm that achieves the 2‑approximation and an O(|E|) algorithm that finds a dominating set in G² no larger than the minimum dominating set of G, based on a strong stable set. The 2‑approximation is best possible, as any δ < 2 would imply P = NP, and the authors also prove the NP‑completeness of the strong stable set decision problem.

Abstract

In this paper we present a 2-approximation algorithm for the k-center problem with triangle inequality. This result is “best possible” since for any δ &lt; 2 the existence of δ-approximation algorithm would imply that P = NP. It should be noted that no δ-approximation algorithm, for any constant δ, 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.