0%

k-median问题在Metric空间上的近似解法

问题定义

先定义一下用到的符号

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

abab