最小顶点覆盖问题
最小顶点覆盖问题是指：给定边集、顶点集及其权重，求权重最小的顶点集，使每条边至少有一个顶点在集合中。
它的整数规划可以写为：
$$
\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 )$ 互补松弛性条件原始对偶方案近似算法的近似比不超过 $\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 。
算法 2
- $ x = 0, y = 0$, 所有边未标记
- 提升所有未标记的边 $y_e$, 直⾄其某⼀顶点的约束变紧: $w_i-\sum_{i\in e}y_e= 0$
- $ x_i = 1$ , 表示将顶点 i 加入覆盖,将与顶点 i 相连的边标记
- 重复步骤 2.3 直至所有的边标记
分析同理
