Given a set of locations $P=\{p_1,p_2,\dots\}$ and a set of facilities $F=\{f_1,f_2,\dots\},|F|\ge k$ on a plane. We want to partition the facilities into $k$ disjoint subsets (each subset has at least one facility). For each subset $F_i,i=1,2,\dots,k$, the cost of location $p\in P$ is the Euclidean distance between $p$ and its nearest facility in $F_i$. The cost of the subset $F_i$ is the sum of the cost of $p$, i.e. $Cost(F_i)=\sum_{p\in P}\min_{f\in F_i} Dis(p,f)$. The total cost is the sum of the costs of all subsets, i.e. $Cost=\sum_{i=1}^k Cost(F_i)$. I think it's an NP-hard problem. But I can't find a good proof. In summary, the problem is: $$ \begin{split} \min_{F_1,F_2,\dots,F_k}\quad &\sum_{i=1}^k\sum_{p\in P} \min_{f\in F_i}Dis(f,p)\\ subject\quad to\quad & F_i\cap F_j=\phi, i\neq j \\ \end{split} $$

Is this an NP-hard problem?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.