问题定义

先定义一下用到的符号

空间中有许多工厂,也有许多客户,集合\(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\).