问题定义
先定义一下用到的符号
空间中有许多工厂，也有许多客户，集合$F$表示工厂集合，集合$C$表示客户集合，y要求给每个客户选择一个工厂，一个工厂可以被多个客户所选择，若一个工厂$x$被客户$y$所选择了，那么称$y$规$x$管理，定义距离函数为$d(x,y)，x \in F, y\in C$表示$y$选择$x$的代价。
具体问题是找到最多$k$个工厂，管理所有的客户，使得距离函数和最小。
这个问题在公制空间上的版本成为Metric K-median问题，是指$d(x,y)$满足正定性，对称性和三角形不等式。
NP？
这其实并不是一个NP-Hard问题，设计近似算法的原因在于加速运算
$C_{2n}^{n}$依旧是多项式复杂度内的问题。
局部搜索算法
首先可以通过简单分析得到选$k$个工厂一定比选择小于$k$个工厂要优。
现在来介绍一种简单的近似算法。
首先随机选择一个集合$S$, 使得$S \subset F$， 并且$|S| = k$， 为了描述方便，扩展一下距离函数的定义令$d(S,y) = \min{d(x,y)},x\in S, y\in C$
然后枚举每个不在$S$中的工厂$z$, 尝试替换$S$中的工厂$x$, 如果能使得答案变得更优就换掉。
这样就会得到一个局部最优解。
实现思路非常简单而且是多项式时间复杂度的做法。
近似度分析
令最优解所选择的工厂集合为$S^{*}$, 其中的元素一般使用$o$来表示。
令上面算法得到的工厂集合为$S$, 其中的元素一般使用$s$来表示。
令$C(x)，x\in F$表示$x$这个元素管理的客户的集合。
首先定义一个术语叫做捕获，如果$C(s) \bigcap C(o) \geq \frac{1}{2}C(o)$则称$s$捕获了$o$。
引理
如果$C(s) \bigcap C(o) < \frac{1}{2}C(o)$，则$C(o)$存在一个自己到自己的满射，使得每一个$x \in C(s)\bigcap C(o)$，可以映射到$C(o) - C(s)$.
我也不知道为什么
定理
该局部搜索算法的近似度为5
证明
首先将$S$根据捕获的最优解中元素的个数分类
$S_{0}$集合表示每个元素不捕获任何最优解中的元素
$S_{1}$集合表示每个元素都捕获最优解中的一个元素
$S_{2}$集合表示每个元素都捕获最优解中的至少两个元素
下面进行$k$次交换，注意并不是连续进行$k$次交换，而是每次都从初始状态进行交换，综合考虑其的代价。
考虑$s \in S_{1}$它所捕获的元素为$o$对于$C(o) \bigcap C(s)$的元素分配给$o$，更严格地这里将$C(o)$的所有元素全部分配$o$(这样相较于之前那种方式并不一定使得当前的答案更加优)，对于$C(o)-C(s)$的元素，因为其中的有个元素为$y$，假设在$S^{}$中分配给了$o^{}$,由于$s$已经捕获了$o$并且因为$s \in S_{1}$于是$o^{}$一定不被$s$所捕获，于是在$C(o^{})$存在一个单射，假设$s^{‘}$为其的像，同时$s^{’} \in C(s^{})$ ,于是将$s$分配给$s^{}$
由三角不等式$$d(y, s^{}) \leq d(y,o^{})+d(o^{},s^{‘}) + d(s^{‘}, s^{})$$
这样一次交换之后$Cost$的变化为
$0 \leq Cost(S-s+o) - Cost(S) \leq \sum_{x \in C(o)} [d(o,x) - d(s,x)] + \sum_{x \in C(s) - C(o)}[d(y,o^{})+d(o^{},s^{‘}) + d(s^{‘}, s^{*}) - d(s, x)]$
接下来考虑剩下的元素该如何交换，可以发现$S_{0}$中的每个元素最多使用$2$次便可以完成最优解中的每个元素被交换一次。
同时可以发现也满足以上不等式。
于是。
将这个不等式累加$k$次，得到$0 \leq Cost(OPT) - Cost(S) + 2*(Cost(OPT) + Cost(OPT) + Cost(S) - Cost(S))$
于是近似度为$5$.