Next:
ND52 MINIMUM K-MEDIAN
Up:
Miscellaneous
Previous:
ND50 MINIMUM K-CLUSTERING
ND51 M
INIMUM
K
-S
UPPLIER
I
NSTANCE
: Complete graph
, distances
satisfying the triangle inequality, center construction cost
and usage weight
w(v)
for each
, cost bound
.
S
OLUTION
: A supplier set of legal cost, i.e., a subset
such that
.
M
EASURE
: The maximum weighted distance from a vertex to its nearest supplier, i.e.,
Good News:
Approximable within 3 [
342
].
Bad News:
Not approximable within 3
for any
[
172
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
, distances
satisfying the triangle inequality, center construction cost
and
usage weight
w(v)
for each
, cost bound
.
such that
.
for any
[
172
].