TDAA 第一章练习题

Exercise 1.1 Partial Set Cover

关键点在于将 $E$ 中元素的贡献为 1 看作为 $p$.

(a): 可以在多项式时间内解决以下 LP problem

$$\begin{array}{rcl} \mathrm{minimize}&\sum_{j=1}^{m}w_{j}x_{j}\\ \mathrm{subject~to}&\sum_{j:e_{i} \in S_{j}} x_{j} \geq p, \quad i=1, \dots, n\\ &x_{j} \geq 0, \quad j=1,\dots,m \\ &x_{j} \leq 1,\quad j=1,\dots,m \end{array}$$

记 $x^{\ast}$ 为 optimal solutions 之一, 令 $f_{i} = \lvert \\{j \vert e_{i} \in S_{j}\\} \rvert$, $f = \max_{i=1,\dots,n}f_{i}$, $I$ 为 solution 得到的集合下标组成的集合. $I$ 起始为空, 当 $x_{j}^{\ast} \geq p / f$ 时就将 $j$ 加入 $I$.

此处 $c(p)=\frac{f}{p}$.

(b): 修改 set cover problem 的 greedy algorithm, 得到算法伪代码如下

$$\begin{array}{ll} 1 & I \leftarrow \emptyset \\ 2 & \hat{S}_{j} \leftarrow S_{j} \quad \forall j \\ 3 & \textbf{while }I\text{ is not a }p\text{-partial set cover }\textbf{do} \\ 4 & \qquad \ell \leftarrow \arg\min_{j:\hat{S}_{j} \not= \emptyset} \frac{w_{j}}{p\lvert \hat{S}_{j} \rvert } \\ 5 & \qquad I \leftarrow I \cup \{\ell\} \\ 6 & \qquad \hat{S}_{j} \leftarrow \hat{S}_{j} - S_{\ell} \quad \forall j \end{array}$$

此处 $f(p) = \sum_{i=1}^{\lfloor p\lvert E \rvert \rfloor } \frac{1}{i}$, 其中 $f(1)=\sum_{i=1}^{\lvert E \rvert} \frac{1}{i}=H_{\lvert E \rvert}$.

Exercise 1.2 Directed Steiner Tree

每个满足 $w_{j} \geq 0 \forall j$ 的 set cover problem 都能转化为对应的 directed steiner tree problem, 即这两个问题等价:

• 将每个元素 $e_{i}$ 看作一个 terminal, 于是 $E \to T$
• 集合 $S_{j}$ 看作经过 $\\{t_{i} | e_{i} \in S_{j} \land e_{i}\to t_{i}\\}$ 且路径总花费为 $w_{j}$ 的一条路径 $p_{j}$, 注意可以添加 cost 不同的重边, 因此 $S_{j} \to p_{j}$ 的转化是可行的
• 要求找到路径的下标集合 $P$ 使得它表示的路径包含了 $T$ 中的所有 terminal, 这与要求找到 $S$ 的下标集合使得它构成一个 set cover 等价
• 目标是最小化 $\sum_{j \in P}c_{j}$ 其中 $c_{j}$ 表示路径 $p_{j}$ 的 cost 与最小化 $\sum_{j \in I}w_{j}$ 其中 $I$ 选中的 $S$ 下标集合等价

因此 set cover problem 的每一组解都在 directed steiner tree problem 有对应的解. 根据书中定理 1.14, 可以得出存在某些常数 $c$, 没有能解决 directed steiner tree problem 的 $c \log|T|$-approximation algorithm, 除非 $\mathrm{P} = \mathrm{NP}$.

Exercise 1.3 Metric Asymmetric TSP

这个 flash 怎么总是开坑不填完啊👿