Next: MINIMUM K-CLUSTERING Up: Miscellaneous Previous: MINIMUM BROADCAST TIME Index

### MINIMUM K-CENTER

- INSTANCE: Complete graph and distances satisfying the triangle inequality.

- SOLUTION: A k-center set, i.e., a subset with |C|=k.

- MEASURE: The maximum distance from a vertex to its nearest center, i.e., .

- Good News: Approximable within 2 [237].

- Bad News: Not approximable within 2 for any [247] and [383].

- Comment: Not in APX if the distances do not satisfy the triangle inequality [233]. 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 [301]. 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 [53]. 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 [141]. 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 [310]. If the vertices lie in Rd 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 [190].

  The vertex weighted version, where the objective is to minimize the maximum weighted distance d(v,c)w(v), is approximable within 2 [386]. 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 [383]. 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 [387]. 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) [294]; it is not approximable within for any [325]. The asymmetric k-center problem, where d(vi,vj) might be different from d(vj,vi), is approximable within [436].

- Garey and Johnson: Similar to ND50

Next: MINIMUM K-CLUSTERING Up: Miscellaneous Previous: MINIMUM BROADCAST TIME Index