Next: MINIMUM FACILITY LOCATION
Previous: MINIMUM DIAMETERS DECOMPOSITION
satisfying the triangle inequality.
A set of k facilities, i.e., a subset
The minimum distance between two facilities, i.e.,
- Good News:
Approximable within 2 .
- Bad News:
Not approximable within 2
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 .
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