- INSTANCE:
Complete graph
and distances
satisfying the triangle inequality.
- SOLUTION:
A set of
*k*facilities, i.e., a subset with . - MEASURE:
The minimum distance between two facilities, i.e.,
.

*Good News:*Approximable within 2 [421].*Bad News:*Not approximable within 2 for any [421].*Comment:*Not in APX if the distances do not satisfy the triangle inequality. MAXIMUM EDGE SUBGRAPH is the variation where the measure is the average distance between any pair of facilities [421]. Variation in which we allow the points in*F*to lie in edges (considered as curves) is also approximable within 2 and is not approximable within [449].