I
NSTANCE
:
Finite set
X
, a distance
for each pair
.
The distances must satisfy the triangle inequality.
S
OLUTION
:
A partition of
X
into disjoint subsets
.
M
EASURE
:
The largest distance between two elements in the same subset, i.e.,
.
Good News:
Approximable within 2 [
139
] and [
172
].
Bad News:
Not approximable within 2
for any
[
139
] and [
172
].
Comment:
The same positive and negative results are valid for
the geometric (Euclidean)
k
-clustering problem in 3
dimensions [
139
]
and for rectilinear
k
-clustering problem in 2 dimensions.
The geometric
k
-clustering problem in 2 dimensions is not
approximable within 1.969 [
102
].
Other variants are also studied in this paper.
for each pair
.
The distances must satisfy the triangle inequality.
.
.
for any
[
139
] and [
172
].