Exercises 1

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\).

Lemma

The collection of subsets \(S_{j}, j \in I\) is a set cover.

Proof

假设存在元素 \(e_{i}\) 没有被包含, 则有 \(x_{j} < p / f, \forall j:e_{i} \in S_{j}\).

于是有

\[\sum_{j:e_{i}\in S_{j}} x_{j} < \sum_{i=1}^{f_{i}} p / f = p \cdot \frac{f_{i}}{f} \leq p\]

与 LP 的约束条件不符, 因此不存在未被 cover 的元素, 得证.

Theorem

The rounding algorithm is a \(f / p\)-approximation algorithm for the partial set cover problem.

Proof

记 \(Z_{LP}^{*}\) 为 \(\sum_{j=1}^{m} w_{j}x_{j}^{\ast}\), \(x\) 为上述 rounding algorithm 的整数解.

\[\begin{aligned}\sum_{j \in I}w_{j} &= \sum_{j \in I}w_{j} \cdot x_{j}^{\ast} \cdot \frac{1}{x_{j}^{\ast}} \\ &\leq \sum_{j \in I} w_{j}\cdot x_{j}^{\ast} \cdot \frac{f}{p} \\ &\leq \frac{f}{p} \sum_{j=1}^{m} w_{j}x_{j}^{\ast} \\ &= \frac{f}{p} Z_{LP}^{\ast} \\ &\leq \frac{f}{p} OPT \end{aligned}\]

因此上述 rounding algorithm 是 \(f / p\)-approximation.

此处 \(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} \]

Theorem

The above algorithm is an \(H_{\lfloor p\lvert E \rvert\rfloor}\)-approximation algorithm for the partial set cover problem.

Proof

while 循环的过程与 set cover 的 greedy algorithm 相同, 使用与书上分析相同记号,依然有

\[w_j \leq \frac{n_{k}-n_{k+1}}{n_{k}}\mathrm{OPT}\]

于是

\[\begin{aligned}\sum_{j \in I}w_{j} & \leq \sum_{k=1}^{\ell} \frac{n_{k} - n_{k + 1}}{n_{k}}\mathrm{OPT} \\& \leq \mathrm{OPT}\cdot \sum_{k=1}^{\ell}\left( \frac{1}{n_{k}} + \frac{1}{n_{k}-1} + \cdots + \frac{1}{n_{k+1}+1} \right) \\& = \mathrm{OPT} \cdot \sum_{i=1}^{\lfloor p\lvert E \rvert \rfloor } \frac{1}{i} \\& = H_{p\lvert E \rvert }\cdot\mathrm{OPT}\end{aligned}\]

此处 \(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