Next: MINIMUM K-MEDIAN Up: Miscellaneous Previous: MINIMUM K-CLUSTERING SUM Index

### MINIMUM K-SUPPLIER

- 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 [440].

- Bad News: Not approximable within 3 for any [237].