and distances
satisfying
the triangle inequality.
with
|C|=k
.
.
for any
[
179
] and [
295
].
[
36
].
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 [
102
].
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
[
236
].
The vertex weighted version, where the objective is to minimize the
maximum weighted distance
d(v,c)w(v)
, is approximable within 2
[
298
].
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 [
295
].
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
[
299
].
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)
[
220
].
The asymmetric
k
-center problem, where
might be different from
, is approximable within
[
339
].
Viggo Kann