MINIMUM K-CENTER

• INSTANCE: Complete graph $G=\left(V,E\right)$ and distances $d(v_i,v_j)\in N$ satisfying the triangle inequality.

• SOLUTION: A k-center set, i.e., a subset $C \subseteq V$ with $\vert C\vert=k$.

• MEASURE: The maximum distance from a vertex to its nearest center, i.e., $\max\limits_{v\in V} \min\limits_{c\in C} d(v,c)$.

  
  

• Good News: Approximable within 2 [202] and [254].

• Bad News: Not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [262] and [404].

• Comment: Not in APX if the distances do not satisfy the triangle inequality [250]. MINIMUM CAPACITATED K-CENTER, the variation in which the number of vertices each center can serve is bounded by a constant L, is approximable within 5 [318]. The converse problem, where the maximum distance from each vertex to its center is given and the number of centers is to be minimized, is approximable within $\log L+1$ [56]. The geometric k-center problem, where the vertices lie in the plane and the geometric metric is used, is approximable within 2, but is not approximable within 1.822 [152]. Variants of the geometric k-center problem are also studied in the paper. The rectilinear k-center problem, where the vertices lie in the plane and the $L_\infty$ metric is used, is approximable within 2, but is not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [327]. If the vertices lie in $R^d$ and the Euclidean or $L_\infty$ metric is used the problem admits a PTAS whose time is exponential in k [1]. Approximable within 2 in any metric space [202].

  The vertex weighted version, where the objective is to minimize the maximum weighted distance d(v,c)w(v), is approximable within 2 [407]. It is not approximable within 2$-\varepsilon$ even if the distances are induced by a planar graph of maximum degree 3 with edge lengths 1 and vertex weights 1 [404]. MINIMUM ABSOLUTE K-CENTER, the variation in which we allow the points in C to lie in edges (considered as curves) is also approximable within 2 and is not approximable within $2-\varepsilon$ [408]. MINIMUM -ALL-NEIGHBOR K-CENTER, the variation in which we want to minimize the distance from each vertex to $\alpha\ge 2$ of the k centers, is approximable within 2 when $\alpha\in\{2,3\}$ and within 3 otherwise (even for the vertex weighted version) [311]; it is not approximable within $2-\varepsilon$ for any $\varepsilon >0$ [341]. The asymmetric k-center problem, where $d(v_i,v_j)$ might be different from $d(v_j,v_i)$, is approximable within $O(\log^*\vert V\vert)$ [459].

• Garey and Johnson: Similar to ND50