MAXIMUM K-FACILITY DISPERSION

• INSTANCE: Complete graph $G=\left(V,E\right)$ and distances $d(v_i,v_j)\in N$ satisfying the triangle inequality.

• SOLUTION: A set of k facilities, i.e., a subset $F\subseteq V$ with $\vert F\vert=k$.

• MEASURE: The minimum distance between two facilities, i.e., $\min\limits_{f_1,f_2\in F} d(f_1,f_2)$.

  
  

• Good News: Approximable within 2 [421].

• Bad News: Not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [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 $3/2-\varepsilon$ [449].