Next: MINIMUM FACILITY LOCATION Up: Miscellaneous Previous: MINIMUM DIAMETERS DECOMPOSITION Index

### MAXIMUM K-FACILITY DISPERSION

- INSTANCE: Complete graph and distances satisfying the triangle inequality.

- SOLUTION: A set of k facilities, i.e., a subset with |F|=k.

- MEASURE: The minimum distance between two facilities, i.e., .

- Good News: Approximable within 2 [399].

- Bad News: Not approximable within 2 for any [399].

- 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 [399]. 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 [426].