创新实训个人记录：metric k-center

• 一些概念
• • k-center（k-中心）
  • dominating set(支配集)
  • independent set(独立集)
  • 独立集&&支配集
  • k-中心&&支配集
  • square of graph （$H^2$）
• 开始证明
• • dom(H)的下限（$H$的支配集&&$H^2$的独立集）
  • 算法
  • 近似比
  • 近似比最优证明

一些概念

k-center（k-中心）

问题来源：给定n个具有指定城市间距离的城市，选择其中k个城市来放置仓库，以最大程度地减少城市与其最近的仓库之间的最大距离。我们在metric的情况下考虑这个问题，即，满足三角不等式；不然的话，找不到一个近似因子α（n），α（n）是任意可计算的函数（第4章有讲到这个证明）。输入<G,k,d>，是否能找到一个集合，最多k个顶点，使剩下n-k个顶点与这k个顶点的最大距离≤d；是一个NP-hard问题。

“最小化”“最大的”“最小距离”：先讲“最小距离”，我们已经确定了k个城市作为仓库，那么对于剩下的n-k个城市中的每一个城市，与这k个城市，有一个最小距离，比如城市A，与这k个城市之间的城市B距离最小，那么城市A与城市B的距离就叫做城市A与这k个城市的最小距离；
然后是“最大的”，对于n-k个城市的每一个城市，有一个对于自己的最小距离，那放到这n-k个城市里考虑，就有n-k个最小距离，在这n-k个距离中最大的，即“最大的”“最小距离”；
最后是“最小化”，对于这n-k个最小距离中最大的距离，进行最小化处理。

数学符号表示：令G =（V，E）是一个完全的无向图，边成本满足三角不等式，而k是一个正整数。 对于任何集合S⊆V和顶点v∈V，将connect（v，S）定义为从v到S中顶点的最便宜边的成本。问题是要找到一个集合S⊆V，且|S|= k，以便最小化$ma{x}_v${connect(v,S)}。即我们可以写成 minimizing $\underset{v\in \mathcal{V}}{\max }\underset{s\in \mathcal{S}}{\min }f(x)$

dominating set(支配集)

概念：支配集就是一个点集，在这个图里，除去这个点集外的所有顶点，都与这个点集中至少一个顶点相连。

看这个图，就可以理解支配的概念。
比如图(a)，红色的顶点就是支配集，所有白色的顶点都连着红色的顶点，所以我们称红色顶点支配着白色顶点，称为支配集。支配集问题，就是对于一个给定的图G和一个数k，我们能不能找到一个最小支配集的顶点数≤k。这个问题已经被证明是NP难问题了。我们再看图(b)、(c )，这两个图就是找到了最小支配集的情况，我们可以知道此时对于这个图来说，最小支配集的最大大小k为2。

数学符号表示：对于图H，最小支配集的顶点数用dom(H)表示。

输入<G,k>，能否找到一个顶点数≤k的支配集，是个NP-complete问题。

independent set(独立集)

对于一个图H，它的独立集，就是这个集合中任意两个顶点不相邻。
maximal independent set: 极大独立集，不是任何独立集的子集；就是对于目前这种状况，不能再加点进入独立集了。
maximum independent set: 最大独立集，就是顶点数最多的独立集。
maximum independent set problem: 是否能找到最大独立集。这是一个NP-hard问题。

独立集&&支配集

通过定义，我们可知极大（maximal）独立集是一个支配集。

证明：对于一个极大独立集$I$，如果存在点$v$没有被独立集$I$支配，，即点$v$和独立集$I$之间没有边，那么我们可以把点$v$加入独立集$I$形成一个更大的独立集$I^{\prime }$，这与$I$是极大独立集矛盾。所以我们可推：极大独立集$I$是一个支配集。

k-中心&&支配集

我们可以把k-center问题转化成dominating set问题。
前提：把图G的边排序，以不降序的顺序排，即$cost(e_1)\le cost(e_2)\le \dots \dots \le cost(e_n)$，让$G_i=(V,E_i)$，其中$E_i=e_1,e_2,\dots \dots e_i$。
转化：我们可以把k-中心问题看作，找最小的索引i，使得$G_i$有一个size≤k的支配集。如果$i^{\ast }$是我们找到的最小索引，那么$cost(e_{i^{\ast }})就是$对于k-中心问题的最优解，即我们找到的“最小的 最大的 最小距离”，用OPT表示。
画图举例：

以上图为例，来讨论k中心问题，支配集问题，以及转化关系。

• k中心问题：输入<G,k,d>，是否能找到一个集合，最多k个顶点，使剩下n-k个顶点与这k个顶点的最大距离≤d。我们输入<G,2,3>：不考虑d时，我们有支配集<A,C>、<A,D>、<A,E>；

  • 对于<A,C>，剩下的6-2=4个城市，到这2个城市的最大的最小距离是：max(BA,DC,EA,FA)=EA=2;
  • 对于<A,D>，剩下的6-2=4个城市，到这2个城市的最大的最小距离是：max(BA,CD,EA,FA)=EA=2;
  • 对于<A,E>，剩下的6-2=4个城市，到这2个城市的最大的最小距离是：max(BA,CA,DE,FA)=DE=4;

  对于此题，我们设置d=3，我们找到的满足题意的集合是<A,C>、<A,D>。

• 支配集问题：输入<G,k>，是否能找到一个顶点数≤k的支配集。我们输入<G,2>，有支配集<A,C>、<A,D>、<A,E>。

• k中心问题转化成有附加条件的支配集问题：找最小的索引i，使得$G_i$有一个size≤k的支配集。先把边排序：{CD,AB,AF,AE,AC,BE,CE,DE}，对于边长度{1，1.2，1.5，2，3.2，3.5，4}。找一个最小的索引i，使得$G_i$有一个size≤2的支配集。我们找到的最小的索引i是4，即{CD,AB,AF,AE}，对应的支配集为{A,C}，最优解是AE=2。

找到的最优解是相等的，这也可以表明“转化后有附加条件的支配集问题”等价于“k中心问题”。

转化成功，下面我们就可以直接从“支配集问题”的角度来考虑啦。

square of graph （$H^2$）

对于图H ，有两个点u、v（$u\ne v$），有一条u，v之间的路径，"a path of length at most two"的意思是u和v之间有边，直接相连或者u通过另外一个顶点连着v，我们定义$H^2$为包含边（u，v）的图，这里对这个边没有定义长度，通常这样的图中的边是没有长度的。
比如上图的平方：

开始证明

dom(H)的下限（$H$的支配集&&$H^2$的独立集）

给定图H,$I$是$H^2$的独立集，有$|I|\le dom(H)$。
$dom(H)$是图H中最小支配集的顶点数，我们这里可以假设D是图H中的最小支配集。有两个概念需要解释一下：star、clique。

• 这里有个star的概念，就是每个支配顶点以及被它支配的顶点、支配边共同形成的图，其实是一个二分图，$K_{1,p}$，一个支配顶点，对应着p个被支配的顶点，p≥1。如下图，这是一个star，对于支配顶点A的star，支配集有几个顶点，就有几个star。即，我们假设支配集为D，那么star的个数为|D|。（比如图H中的最小支配集为<A,D>）
  
• 还有一个概念clique，网上翻译成“团”，在我们这里是完全子图的意思。对照着上面的顶点（即图H中的一个star），我们也可以画出clique的图：（可以看出是一个完全子图，因为star中的每个被支配顶点之间都可以通过支配顶点连在一起，如B、C通过A连在一起。）
  
  现在有一个显而易见的事情，在图H中最小支配集D的任意一个star，在图$H^2$中都是一个clique，所以图$H^2$中有|D|个clique。

分析：那么然后，我们回到证明本身。我们要证明的内容是：“给定图H,$I$是$H^2$的独立集，有$|I|\le dom(H)$。” 图$H^2$中的独立集的大小≤图H中的最小支配集的大小，就是说我们可以找到任意图的最小支配集的下限，就是用它的平方的独立集的大小来表示。图H中的最小支配集的大小，是|D|。我们现在要证图$H^2$中的独立集$I$的大小≤|D|。所以我们要先找到图$H^2$中的独立集$I$。

从图$H^2$的clique中找独立集$I$：独立集我们知道，就是这个集合中任意两个顶点不相邻。那么对于一个clique，完全子图来说，每个顶点都彼此相邻，只会存在最多一个顶点属于图H的独立集（0个的情况是，这个子图的顶点与其他子图的顶点相邻，我们取了其他子图的顶点就不再取）。

计算独立集$I$的大小：我们已经知道，图$H^2$中有|D|个clique，那么从每个clique中拿出最多一个顶点，形成独立集，可以说明独立集的大小最多只有|D|。即可证给定图H,$I$是$H^2$的独立集，有$|I|\le dom(H)$。

得到结论：对于任意一个图H，最小支配集大小的下限是该图平方$H^2$的任意一个独立集大小。

算法

思路：

• k-center转化为支配集问题：我们之前已经分析过，k-center问题可以转化为：找最小的索引i成为$i^{\ast }$，使得$G_{i^{\ast }}$有一个size≤k的支配集。OPT=$cost(e_{i^{\ast }})$。（$e_{i^{\ast }}$在{$e_{i^1}$、$e_{i^2}$、$e_{i^3}$……$e_{i^{\ast }}$}中就是“最大的”“最小距离”，然后我们找最小的索引，就相当于“最小的”“最大的”“最小距离”。）

• OPT下限：如第1章所说，我们通常的套路就是，因为算不出来OPT，没法算近似比=近似解/OPT；我们就先算OPT的下限，OPT≥a，然后近似解≤a·c，(c为常数)，然后呢就有近似解≤c·a≤c·OPT，近似解/OPT≤c。所以这里证明的就是套路中的第一步：先算OPT的下限，即$cost(e_{i^{\ast }})$的下限。

• 计算OPT下限：因为我们按照边的大小给边排序索引，那么我们需要找一个合适的j，满足$j<i^{\ast }$，这样就有$cost(e_j)<cost(e_{i^{\ast }})$啦。

• 找合适的下限索引j：因为我们之前已经证明：图H最小支配集大小下限是图$H^2$任意独立集大小，即$|I|\le dom(H)$。也就是说，图H中的|最小支配集|≥图$H^2$的|最大独立集|。即我们可以用图平方上的独立集问题来考虑找到合适的j。

算法内容：

1.构造$G_1^2$,$G_2^2$,…,$G_m^2$。
2.在每个图$G_i^2$中计算最大独立集$M_i$。
3.找到最小索引i，使$|M_i|\le k$，此时，$j=i$。
4.返回$M_j$。

OPT下限定理：对应我们定义的j，$cost(e_j)\le OPT.$
证明：这里证明的就是套路中的第一步：先算OPT的下限。

• 我们在图H中找最小的索引i成为$i^{\ast }$，使得$G_{i^{\ast }}$有一个size≤k的支配集，OPT=$cost(e_{i^{\ast }})$，我们要证的就是$j\le i^{\ast }$。
• j是对于每个图$G_i^2$中最大独立集$M_i$，满足$|M_i|\le k$的最小索引。$i^{\ast }$是使得图$G_{i^{\ast }}$有一个size≤k的支配集的最小索引。 也就是说，我们要证，|图平方最大独立集|≤|图最小支配集|。
• 我们之前的定理已经推出：图H的最小支配集dom(H)≥I，I是图$H^2$中的任意一个独立集，当然也包括最大独立集。定理可证。

直观分析：

• 图$H$和图$H^2$，很明显地，图$H^2$的边更多。
• 如果要求支配集的大小，很显然是在图$H^2$中的支配集|D’|≤图$H$中的支配集|D|。如果要求最大独立集的大小，也很显然是在图$H^2$中的最大独立集|I’|≤图$H$中的最大独立集|I|。而且之前我们有证过，一个图的最大独立集也是这个图的支配集，也符合以上的想法。
• 然后呢，我们之前证过一个定理，图H的最小支配集dom(H)≥I，I是图$H^2$中的一个独立集。也就是说，图$H^2$中的最大独立集|I’|≤图H的最小支配集dom(H)。我们找到的j就是对应着图$H^2$中的最大独立集|I’|，$i^{\ast }$就是对应着图H的最小支配集dom(H)，所以$j\le i^{\ast }$。

近似比

该近似算法可以算出OPT下限，那么就胜利在望了！现在再找个常数，和下限相乘，如果是我们的近似解就没问题啦~

此近似算法的近似比为2，即$近似解/最优解\le 2$。
证明：

• 因为我们之前已经证过：最大独立集也是支配集。那么我们找到的图$H^2$中的最大独立集$I^{\prime }$也是支配集$D^{\prime }$，也有$|D^{\prime }|$个star。即我们找出来的j，对应的$G_j^2$上的最大独立集$M_j$，也是相应的支配顶点。
• 因为我们找到的$e_j$是$M_j$中最长的边，所有在$M_j$中该star的边$cost(e_i)\le cost(e_j)$，根据三角不等式，我们可知所有在$M_j$中的边$cost(e_i)\le 2\cdot cost(e_j)$。
• 又因为我们之前证过$cost(e_j)\le OPT$，所以有$cost(e_i)\le 2\cdot cost(e_j)\le 2\cdot OPT$。

近似比最优证明

即我们要证明对于k-center问题，不存在近似因子2−ε, ε>0。

总结

以上是生活随笔为你收集整理的创新实训个人记录：metric k-center的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。