Next:
ND53 MINIMUM DIAMETERS
Up:
Miscellaneous
Previous:
ND51 MINIMUM K-SUPPLIER
-
I
NSTANCE
:
Complete graph
and distances
.
-
S
OLUTION
:
A
k
-median set, i.e., a subset
with
|V'|=k
.
-
M
EASURE
:
The sum of the distances from each vertex to its nearest median, i.e.,
-
Bad News:
Not in A
PX
[
259
].
-
Comment:
The problem is in A
PX
if a small violation of the
cardinality of the median set is allowed.
-
Garey and Johnson:
ND51
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997