复杂度理论作业2

Posted on 2024-03-13 Edited on 2024-03-19

1.2

问题：对于Steiner Tree 问题，证明，存在一个常数\(c\),使得对于Steiner Tree 问题，没有\(c\log |T|\)-approximation算法，除非\(P=NP\)

证：先证NPC： 1. NP-HARD：考虑从un-weighted set cover归约，对于一个set cover，将根节点向每个集合连一条边权为1的有向边，每个集合再向自己的元素连0权有向边，目标集合设定为所有元素节点。 2. NPC:显然这是NP的

按照课本定理1.14(如果存在一个\(c\),使得如果存在一个set cover的\(c\ln n\)算法，那么\(P=NP\))得证

1.3

a

考虑每个环，对每个点的入度和出度都增加1，因此最终所有点的出度和入度都是一样的，因此是欧拉图。
由于是欧拉图，因此存在一个遍历所有边的环路，故而遍历了所有点，因此图是强连通的。

综上，得到的子图是一个强连通欧拉图。

b

设第 \(i\) 轮后，图上还有 \(n_i\)个节点。第\(i\)轮选择的最小平均值为\(w_i\),令最优解为 \(OPT\)

考虑最优解形成的环： loop 假设第\(i\)轮开始前是如图的，蓝色的点是已经被删去的，由三角形不等式，设这个环的和为\(OPT'\),那么一定有\(OPT' \leq OPT\) 因此\(w_i \leq \frac{OPT'}{n_i} \leq \frac{OPT}{n_i}\),第\(i\)轮的贡献为\(w_i\cdot (n_i-n_{i+1}+1)\),因而总贡献\[\sum (n_i-n_{i+1}+1)\cdot w_i \leq \sum\frac{n_i-n_{i+1}+1}{n_i}\cdot OPT\]

注意到\(\sum\frac{n_i-n_{i+1}}{n_i} \leq H_n\)并且\(\sum\frac{1}{n_i} \leq H_n\)，因此总贡献小于等于\(2H_n\cdot OPT\)

1.5

对于无向图带权set cover问题

列出下列LP:

目标：\(min:z=\sum\limits_{i=1}^{n}w_i \cdot x_i\)

subject to:

\(\forall (u,v) \in E:x_u+x_v \geq1\) \(x_i \geq 0\) 证明，对于该问题的extreme point \(x*\),\(x*_i \in \{0,\frac{1}{2},1 \}\) 证：用反证，如果存在一个extreme point,其中有不在\(\{0,1,\frac{1}{2}\}\)中的\(x\),我们直接对所有小于\(\frac{1}{2}\)且不是0的值减去\(\epsilon\),对所有大于\(\frac{1}{2}\)且不是1的值加上\(\epsilon\),构造出一个新的\(y_1\),然后再对其中有不在\(\{0,1,\frac{1}{2}\}\)中的\(x\),我们直接对所有小于\(\frac{1}{2}\)且不是0的值+\(\epsilon\),对所有大于\(\frac{1}{2}\)且不是1的值-\(\epsilon\)，得到\(y_2\),可以发现\(\frac{y_1+y_2}{2}=x^*\),与\(x*\)是extreme point矛盾

构造一个\(\frac{3}{2}\)-approximation 算法求解平面图set-cover

首先多项式时间跑一遍上面的线性规划，如果一个点的赋值是0或1，那就选或不选，剩下的点都是\(\frac{1}{2}\)的点，它们连的点一定是\(\frac{1}{2}\)或者\(1\)的点，因此，我们考虑所有\(\frac{1}{2}\)的点的导出子图\(G'\)(显然\(G'\)也是平面图),我们的目标是把\(G'\)里的所有点都改成0或1，并且只要满足在\(G'\)里没有0和0共边即可。

对\(G'\)跑四染色(可以多项式)，设四个部分颜色的和分别为\(a,b,c,d\),WLOG. 设\(a\leq b\leq c\leq d\),让\(a,b,c\)里面的点取1，\(d\)的取0。这样我们就得到了\(\frac{3}{2}-approximation\)

正确性：首先肯定没有00共边。

其次，我们设线性规划的最优解是\(x^*\),rounding后的解是\(\hat{x}\),\(G'\)的点集为\(V'\),那么rounding后的答案为\[\sum\limits_{v \notin V'}\hat{x}_v \cdot w_v+\sum\limits_{v\in V'}\hat{x}_v\cdot w_v=\sum\limits_{v\notin V'}x^*_v\cdot w_v+(a+b+c)\],而我们可以发现，\(a+b+c\leq 3d\),因此\[a+b+c= (a+b+c+d)\frac{a+b+c}{a+b+c+d}\leq (a+b+c+d)\frac{1}{1+\frac{d}{a+b+c}}\leq (a+b+c+d)\frac{1}{1+\frac{1}{3}}=\frac{3}{4}(a+b+c+d)\]

故\(\sum\limits_{v\notin V'}x^*_v\cdot w_v+(a+b+c) \leq \sum\limits_{v\notin V'}x^*_v\cdot w_v+\frac{3}{2} \sum\limits_{v\in V'}x^*_v\cdot w_v \leq \frac{3}{2}LP \leq \frac{3}{2}OPT\)