提问于:
浏览数:
2133
The metric k-median \cite{charikar2002constant} problem is NP-hard. Given a metric space X, a group of customers $C \in X$ and a group of facilities $F \in X$, it selects open $k$ facilities in $F$ to reduce the total distance from each customer to the nearest open facilities. Considering that the metric k-median problem is given a complete graph ${G^'} = \left\langle {{V^'},{E^'}} \right\rangle$, we build the SDN-based IoT network $G = \left\langle {V \cup S \cup B,E} \right\rangle$ based on ${G^'}$, in which $V \cup S \cup B = {V^'}$, $E = {E^'}$. The BCDP is to select a suitable set of facilities in $G$ to minimize network latency and open cost, which is the same as the metric k-median problem. So the BCDP proved to be NP-hard.

有没有大佬知道什么原因