- INSTANCE:
Complete graph
and distances
satisfying
the triangle inequality.
- SOLUTION:
A
*k*-center set, i.e., a subset with . - MEASURE:
The maximum distance from a vertex to its nearest center, i.e.,
.

*Good News:*Approximable within 2 [202] and [254].*Bad News:*Not approximable within 2 for any [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 [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 metric is used, is approximable within 2, but is not approximable within 2 for any [327]. If the vertices lie in and the Euclidean or 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 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 [408]. MINIMUM -ALL-NEIGHBOR*K*-CENTER, the variation in which we want to minimize the distance from each vertex to of the*k*centers, is approximable within 2 when and within 3 otherwise (even for the vertex weighted version) [311]; it is not approximable within for any [341]. The asymmetric*k*-center problem, where might be different from , is approximable within [459].*Garey and Johnson:*Similar to ND50