Next: MINIMUM K-MEDIAN
Up: Miscellaneous
Previous: MINIMUM K-CLUSTERING SUM
  Index
- INSTANCE:
Complete graph
,
distances
satisfying the triangle inequality, center construction cost
and
usage weight w(v) for each
,
cost bound
.
- SOLUTION:
A supplier set of legal cost, i.e., a subset
such that
.
- MEASURE:
The maximum weighted distance from a vertex to its nearest supplier, i.e.,
- Good News:
Approximable within 3 [463].
- Bad News:
Not approximable within 3
for any
[254].
Viggo Kann
2000-03-20