MAXIMUM K-FACILITY LOCATION

• INSTANCE: Complete graph $G=\left(V,E\right)$ and profits $p(v_i,v_j)\in N$.

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

• MEASURE: The maximum total profit, i.e., $\sum\limits_{v\in V}\max\limits_{f\in F} p(v,f)$.

  
  

• Good News: Approximable within e/(e-1) [122].