原始对偶方法近似-最小顶点覆盖问题

最小顶点覆盖问题

最小顶点覆盖问题是指：给定边集、顶点集及其权重，求权重最小的顶点集，使每条边至少有一个顶点在集合中。

它的整数规划可以写为：

\[ \begin{align*} \min \sum^n_{i=1} &w_ix_i \\\\ \mathbf{s.t.}\ \ x_i + x_j \ge 1 &,\forall(i,j)\in E \\\\ x_{ij} \in& \{0,1\} \end{align*} \]

线性规划 Rounding

可以将整数规划问题 $IP$ 转化为线性规划问题 $LP$ 。对于最小化问题，线性规划的最优解 $C_{LP} $ 小于等于整数规划的最优解 $ C_{IP}$ 。此时，若对线性规划的最优解进行 rounding 从而得到一个可行解，若知道 rounding 的近似比为 $\alpha$，则可以得到该算法的近似比：

\[ \frac{C_{\mathrm{appro}}}{C_{IP}} \le \frac{C_{\mathrm{appro}}}{C_{LP}} \le \alpha \]

顶点覆盖问题为例

可以将上述整数规划转化为线性规划问题

\[ \begin{align*} \min \ &\sum^n_{i=1} w_ix_i \\\\ \mathbf{s.t.}\ \ x_i + x_j \ge 1 &,\forall(i,j)\in E \\\\ x_{ij} &\ge 0 \end{align*} \]

对线性规划的最优解进行简单的 rounding：设 $x^*$ 为线性规划的最优解， \[ \begin{align*} x^\*=\left[ \begin{array}{}x_1^\*\\\\...\\\\x_n^\* \end{array} \right]\rightarrow \mathbf{rounding}\rightarrow \bar{x}=\left[ \begin{array}{}\ 1\\\\\ 0\\\\...\\\\\ 1 \end{array} \right],\bar{x} _i = \begin{cases}1, &x _ i^\*\ge\frac{1}{2}\\\\0,&x _ i^\*<\frac{1}{2}\end{cases} \end{align*} \]

此时有： \[ \begin{align*} C _ {LP} &= \sum _ {i=1}^n w_ix_i^* \\\\ C _ {appro} &= \sum _ {i=1}^n w_i\bar x_i \le 2 \sum_{i=1}^n w_ix_i^* =2 C _ {LP}\\\\ \frac{C _ {\mathrm{appro}}}{C _ {IP}} &\le \frac{C _ {\mathrm{appro}}}{C _ {LP}} \le 2 \end{align*} \]

因此，该算法的近似比为 2 。

但是，解线性规划太麻烦了。。。

原始对偶方法

回忆一下之前学的原始对偶方法：考虑原问题($LP$) 为：

\[ \begin{align*} \min_x \sum _ {j=1}^nc_jx_j \\\\ \mathbf{s.t.}\ \ \sum _ {j=1}^na_{ij}x_j\ge b_i \\\\ x_j \ge 0 \end{align*} \]

对偶问题 ($DLP$)为

\[ \begin{align*} \max_y \sum _ {i=1}^m b_iy_i \\\\ \mathbf{s.t.}\ \ \sum _ {i=1}^m y_ia_{ij} \le c_j\\\\ y_i\ge 0 \end{align*} \]

互补松弛条件：设 $x$ 和 $y$ 分别为原线性规划和对偶问题的可行解， $x$ 和 $y$ 为最优解当且仅当原问题的可行解 $x$ 与 $y$ 满足:
(PCS : primer complementary slackness; DCS: Dual complementary slackness)

\[ \begin{align*} \mathbf{PCS}：\left(c_j-\sum _ {i=1}^my_ia_{ij}\right)x_j = 0\\\\ \mathbf{DCS}：\left(b_i-\sum _ {j=1}^na_{ij}x_j\right)y_i = 0 \end{align*} \]

线性规划的原始对偶算法为:

从可行的对偶问题解和非可行的原问题解开始；
迭代修改对偶解，在满足互补松弛性的前提下修改原始解，使原始解逐步可行；
当互补松弛性条件和可行性同时满足时，即得到最优的原问题解和对偶问题解

松弛的互补松弛条件：设 $x$ 和 $y$ 分别为原线性规划和对偶问题的可行解，$\alpha\ge 1, \beta \ge 1$

\[ \begin{align*} \alpha -松弛：x_j = 0 \quad \mathbf{or}\quad \frac{c_j}{\alpha}\le\sum _ {i=1}^my_ia_{ij}\le c_j\\\\ \beta -松弛：y_i = 0 \quad \mathbf{or}\quad b_i\le\sum _ {j=1}^nx_ja_{ij}\le \beta\cdot b_i \end{align*} \]

原始对偶方法近似算法为:

从可行的对偶问题解和非可行的原问题整数解开始；
迭代修改对偶解，在满足松弛的互补松弛性与整数性的前提下，使原始解逐步可行；
当 $( \alpha , \beta )$ 互补松弛性条件和可行性同时满足时，即得到最优的原问题的一个近似解

定理: 满足 $( \alpha , \beta )$ 互补松弛性条件原始对偶方案近似算法的近似比不超过 $$ 。

\[ \begin{align*} C_{\mathrm{appro}} &= \sum_{j=1}^nc_jx_j\\\\ &\le \alpha\cdot \sum_{j=1}^n\left( \sum_{i=1}^ma_{ij}y_i\right)x_j\quad(\mathrm{if}\ x_j\neq 0, c_j\le \alpha\cdot\left( \sum_{i=1}^ma_{ij}y_i\right))\\\\ &=\alpha \cdot\sum_{i=1}^m\left( \sum_{j=1}^na_{ij}x_j\right)y_i\\\\ &\le \alpha\cdot\beta\cdot \sum_{i=1}^m b_iy_i\quad(\mathrm{if}\ y_i\neq 0, \sum_{j=1}^na_{ij}x_j\le \beta\cdot b_i)\\\\ &\le \alpha\cdot\beta\cdot C_{LP} \quad(弱对偶定理)\\\\ &\le \alpha\cdot\beta\cdot C_{IP} \end{align*} \]

顶点覆盖问题为例

顶点覆盖问题的对偶问题为：

\[ \begin{align*} \max &\sum_{e\in E}y_e\\\\ \mathbf{s.t.}\quad \sum_{i\in e}y_e&\le w_i,\forall i \in V\\ y_e &\ge 0 \end{align*} \]

互补松弛条件为：

\[ \begin{align*} x_i(w_i-\sum_{i\in e}y_e) = 0\\\\ y_e(x_i+x_j-1) = 0 \end{align*} \]

可以将互补松弛条件松弛为：

\[ \begin{align*} x_i = 0 \quad \mathbf{or}\quad w_i=\sum_{i\in e} y_e\\\\ y_e = 0 \quad \mathbf{or}\quad 1\le x_i+x_j\le 2 \end{align*} \]

此时 $\alpha= 2, \beta = 1$ ，因此，若找到满足以上条件的可行整数解，近似比为 2

迭代算法

[从可行的对偶问题解和非可行的原问题整数解开始]
$ x = 0, y = 0$, 所有边未标记
[ 修改对偶解，满足松弛的互补松弛条件]
任选⼀条未标记的边 $e$ ,提升 $y_e$, 直⾄其某⼀端顶点的约束变紧: $w_i-\sum_{i\in e}y_e= 0$
[修改原始解，使原始解逐步可行]
$ x_i = 1$ , 表示将顶点 i 加入覆盖,将与顶点 i 相连的边标记
重复步骤 2.3 直至所有的边标记

所有的边都被标记表示得到了一个顶点覆盖集合, 由于 a) $ x_i = 1$ 时 $w_i-\sum_{i\in e}y_e= 0$ 成立; b) 一条边只连接两个顶点, $1\le x_i+x_j\le 2$ 。此时满足松弛的互补松弛条件, 因此该算法的近似比为 2 。