MAXIMUM K-FACILITY LOCATION

Next: MINIMUM K-SWITCHING NETWORK Up: Miscellaneous Previous: MINIMUM FACILITY LOCATION Index

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].

Viggo Kann
2000-03-20