复杂度理论作业3

Posted on Edited on

2.1

a

对于每个节点 \(d_i \in D\),令 \(c(d_i)\)为 \(F\) 中离\(d_i\)最近的点。令这个问题最优解为\(OPT\),可以注意到 \(dis(d_i,c(d_i)) \leq OPT\)

如果

  1. \(|D| \leq k\),那么取 \(S=\{c(d_i)\}\),注意到这样的解显然是不劣于 \(OPT\)

  2. \(|D| > k\),那么对 \(D\)执行 k-center的2近似算法，设最终结果为\(\{d'_1,d'_2,...d'_k\}\)。取\(S=\{c(d'_i)\}\)

对于任何一个\(v \in F\),如果\(dis(v,D) \geq 2OPT\)，根据k-center的2近似算法表明，\(\forall i,j \in [k],dis(d'_i,d'_j)\geq 2OPT\)但是考虑最优解的局面，每个最优解必然以\(OPT\)为半径覆盖了所有点，由于\(|D|>k\),根据抽屉原理，一定有两个cunstomers 处于同一个覆盖圆里面，那么他们的距离将会小于 \(2OPT\),矛盾。

因此 \(\forall v\in F,dis(v,S) \leq 2OPT\),又因为 \(\forall i \in [k],dis(d'_i,c(d'_i)) \leq OPT\),由三角不等式，\(dis(v,S)\leq 3OPT\),得证

b

如果存在小于3的常比近似

考虑解决k-dominant 问题，对于给定的无向图 \(G=(V,E)\)，用下述方法构造新图：对于原图中每个节点 \(v_i\),创建俩节点\(f_i,d_i\)分别为supplier和customer，所有supplier内部两两连边权为2的边，对于每个\(v_i\)，设在\(G\)中它连了\(S_i\)的点，那么\(f_i\)向\(\{d_j| j\in S_i \}\)都连一个边权为1的边，其它没连的边都连边权为3的边。

在这个新图上跑\(\alpha-app(\alpha <3 )\)的k-supplier算法，如果OPT是1，那么表明原图存在k-dominant，近似算法会给出\(\alpha\)的解，但是这样的解一定只能是1，因此这就完美解决了k-domiant这个NPC。

2.2

显然要把jobs两两配对

将\(2m\)个jobs降序排序:

这样构造出的最优解是\(C_{max}=p_i+p_{2m+1-i}\),假设有另一种分组方式使得最大值\(C'_{max} < C_{max}\),那么\(p_i\)的另一半\(p_k\)一定有 \(p_k<p_{2m+1-i}\),这说明\([i-1]\)中一定有货物无法匹配到\([2m+2-i]\)中的job（图中蓝色那一对），那么这一对的和显然大于 \(p_i+p_{2m+1-i}\)也就是大于\(C_{max}\), 矛盾!

2.3

将解分为两部分，一部分是没有机器idle的时间们，设这一段总时长为\(a\),显然\(a \leq \frac{\sum p_i}{m}\leq OPT\)

第二段是有机器空闲的时间段，为什么机器会空闲呢，因为在有向图上，每个待加入的节点都在被之前的点牵制，因此这些空闲时刻一定有一串jobs满足\(j_1 \prec j_2 \prec ... \prec j_k\),显然这个和不超过\(OPT\)

最后总和\(=a+b\leq OPT\)

2.5

a

考虑原问题的OPT情形：

直接按照dfs序对terminal节点排序为\(T_1,T_2...T_k\)

由三角形不等式知\(\sum\limits_{i=1}^{k-1}dis(T_i,T_{i+1})\leq 2OPT\),所有terminal节点按此方式连城的链一定是某棵 \(G'\)的生成树，因此最小生成树的值一定不劣于\(2OPT\)

b

\(c'\)满足三角形不等式，因此按照上题结论依然是2近似

2.9

2.10

设最优解的集合为\(O\),\(f(O)=OPT\) ## Lema \(\exist i \notin S,st.f(S+i)-f(S)\leq\frac{f(O)-f(S)}{k}\)

证：设\(O-S=\{i_1,i_2...i_t\}\)，那么\((O)-f(S)=f(S+i_1)-f(S)+f(S+i_1+i_2)-f(S+i_1)...f(O)-f(S+i_1+i_2..i+{t-1})\)

注意到 \[f(S+\sum\limits_{j=1}^{p}i_j)+f(S)\leq f(S+\sum\limits_{j=1}^{p-1}i_j)+f(S+i_p)\](次模性)

因此 \[f(S+\sum\limits_{j=1}^{p}i_j)-f(S+\sum\limits_{j=1}^{p-1}i_j)\leq f(S+i_p)-f(S)\leq f(S+i)-f(S)\] 故 \[f(O)-f(S) \leq t(f(S+i)-f(S)) \leq k(f(S+i)-f(S))\]

引理得证。

回到原问题，记\(S^t\)为第\(t\)次之后选的集合，那么有 \(f(S^t)\geq (1-\frac{1}{k})f(S^{t-1})+\frac{1}{k}f(O)\),变形

\[f(S^t)-f(O)\geq (1-\frac{1}{k})(f(S^{t-1}-f(O)))\]

故

\(f(S^k)\geq (1-(1-\frac{1}{k})^k)f(O) \geq (1-\frac{1}{e})f(O)\)

2.11(a)

设\(f(S)\)为选择集合为\(S\)时覆盖的集合大小，显然f满足单调性。

对于任意两集合 \(A,B \subseteq E\),显然 \(f(A)-f(A \cap B)\leq f(A \cup B)-f(B)\),因而满足次模性

于是有\(1-\frac{1}{e}\)近似