呈之前的討論，對於 WSC 問題，我們有了利用 LP solver 去對解做 deterministic rounding 及 randomized rounding 的演算法，解法的共通點是必須要先 run 過 LP solver (雖然理論上是 POLY ，實務上現行的 solver 也很有效率)，但我們仍想問說，是否存在不須使用 LP solver 的演算法呢？ 而這也是這講所要提到的 Primal-Dual Method 。
至於實務上的好處嘛…，節錄官方(?)說法如以下:
While linear programs are efficiently solvable, and algorithms for them are quick in practice, special purpose algorithms are often much faster
Rewrite to Dual Form
As primal-dual LP mentioned, the dual LP is
$$ \max \sum_{j=1}^{n} \alpha_j \quad s.t. \begin{cases} \sum_{e_j \in S_i} \alpha_j \leq \text{cost}(S_i) \; \forall i \\ \alpha_j \geq 0 \end{cases} $$
Remark: \
寫出 dual form 的直觀方法是，原先的 constraint 會變 objective ，而 objective 會變 constraint 。 \
像這個例子為 我們想儘量 maximize 原先 constraint 中 $\underset{i: e_j \in S_i}{\sum} x_i \geq 1$ 乘上的那個係數 $\alpha_j$ ( 想讓原 objective 的下界越 tight 越好，而我們有 $j$ 個這樣的式子)，但對每個 $i$ 來說，係數合不能超過原先 objective 的 $x_i$ 係數 (也就是上方的 constraint ，而我們有 $i$ 個這樣的限制)。
Correctness of Approx. Ratio
利用 Weak Duality Theorem, $\forall , \text{feasible} , \mathbf{x}, \mathbf{\alpha}$我們有
$$ \sum_{i=1}^m \, \text{cost}(S_i) \cdot x_i \color{red}{\geq} \sum_{(i,j): e_j \in S_i} \, \alpha_j \cdot x_i \color{green}{\geq} \, \sum_{j=1}^{n} \, \alpha_j $$
雖然 form 看起來簡單一些了，但要找出符合 complentary slackness 的 dual OPT 還是很難，所以我們做些 relaxation。
Relaxed Complementary Slackness
$$ \begin{cases} \color{red}{\geq}: \forall i, \, \text{either} \, x_i = 0 \, \text{or} \, \boxed{\color{red}{\frac{1}{A} \, \text{cost}(S_i)} \leq \sum_{j: e_j \in S_i} \alpha_j \, \leq \text{cost}(S_i)}\\ \color{green}{\geq}: \forall j, \, \text{either} \, \alpha_j = 0 \, \text{or} \, \boxed{\color{green}{B} \, \geq \, \sum_{i: e_j \in S_i} x_i \, \geq \, 1} \end{cases} $$
Then, we have
$$ \boxed{\sum_j \alpha_j \, \leq \, \sum_{i}\text{cost}(S_i) \cdot x_i \leq \color{red}{A}\color{green}{B} \sum_{j}\alpha_j} $$
如我們之前對題目做的假設，如果每個 element 都被 $\leq l$ 個 subset 蓋住的話，相當於是設 $A = 1, B = l$，可以 derive 出一個 $l$-approx. algorithm。
Algorithm - Primal-Dual Method
Core Concept
慢慢更動 dual solution 的 variable $\alpha_j$ 並搭配 complentary slackness (儘量去 satisfy，不行就 relax 得更鬆) ，利用此去轉換出 primal solution 。
一個可行的 Algorithm
Initially, $\alpha_j = 0 ; \forall j$
- Pick any uncovered element $e_j$
- Increase $\alpha_j$ until $\exists , i ; s.t ; \underset{e_j \in S_i}{\sum} \alpha_j , = , \text{cost}(S_i)$ $\Rightarrow , \color{green}{ S_i , \text{is tight}}$ ($\color{red}{\text{更動 dual sol. } , \land , \text{搭配 C.S.}}$)
- Add all $\color{green}{\text{tight}} , S_i$ to set cover ($\color{red}{\text{轉換出 primal sol.}}$)
Repeat above procedure until all elements are covered
comments powered by Disqus