Rounding Linear Programs

1 Vertex Cover

问题表示

整数线性规划:

$\begin{aligned} {\text{minimize}} &&&\sum_{v\in V}x_{v}\\ {\text{subject to}} &&&\sum _{v\in e}x_v\ge 1,&&e\in E,\\ &&&x_{v}\in \{0,1\},&&v\in V. \end{aligned}$

解整数线性规划是NP难的.

线性规划的一般形式

matrix $A=\{a_{ij}\}$, sets $M\subseteq [m]$, $N\subseteq [n]$.

$\begin{aligned} {\text{maximize}} &&&c^\top x\\ {\text{subject to}} &&&a_i^\top x=b_i,&&i\in M,\\ &&&a_i^\top x\ge b_i,&&i\in \overline M,\\ &&&x_{j}\ge 0,&&i\in N,\\ &&&x_{j}\text{ unconstrained},&&i\in \overline N,\\ \end{aligned}$

规范形:
$m\times n$矩阵$A$,

$\begin{aligned} {\text{maximize}} &&&c^\top x\\ {\text{s.t}} &&&Ax\ge b.\\ \end{aligned}$

转化方式:
等于限制变为大于等于和小于等于, 小于等于加负号;
无限制的变量变成两个非负变量之差.
几何解释: 超空间内的凸多面体

Relaxation & Rounding

线性松弛:

$\begin{aligned} {\text{minimize}} &&&\sum_{v\in V}x_{v}\\ {\text{subject to}} &&&\sum _{v\in e}x_v\ge 1,&&e\in E,\\ &&&x_{v}\in [0,1],&&v\in V. \end{aligned}$

线性规划可以在线性时间内解.

近似:
线性规划解$x^*\in [0,1]^V$, 整数规划解$\hat x\in \{0,1\}$.

$\hat x_v=\begin{cases} 1 & \text{if }x_v^*\ge 0.5\\ 0 &\text{otherwise} \end{cases}$

因为

$\sum_{v\in e}x_v^* \ge 1 \to \sum_{v\in e}\hat x_v\ge 1$

所以得到的解依然是可行的.
又因为$\hat x_v\le 2x_v^*$, 所以

$OPT\ge OPT_{LP} = \sum_{v\in V}x_v^*$ $SOL=\sum_{v\in V}\hat x_v\le 2 \sum_{v\in V}x_v^*\le 2\cdot OPT$

一般步骤

表示为整数规划
松弛为线性规划
找到线性规划的最优解
近似到可行解
证明离整数规划最优解不远 $\text{Integrality Gap}= \sup_I \frac{OPT(I)}{OPT_{LP}(I)}$ 对于点覆盖问题, Integrality Gap为2.

2 MAX-SAT

随机解

一个子句 $C=(l_1\lor l_2\lor \cdots\lor l_k )$, $l_j\in \{x_i,\neg x_i\}$

$\Pr[C \text{ is satisfied}]=1-2^{-k}\ge 1/2$ $\mathbb E[\text{number of satisfied clauses}] \ge \frac{m}{2}\ge \frac{1}{2}OPT$

整数规划

布尔变量$x_1,x_2\cdots,x_n\in \{0,1\}$
$S_j^+:$ set of $i$ that $x_i$ is in $C_j$
$S_j^-:$ set of $i$ that $\neg x_i$ is in $C_j$
$C_j$ is satified <==> $\sum_{i\in S_j^+}x_i +\sum_{i\in S_j^-}(1-x_i)\ge 1$
整数规划:

$\begin{aligned} {\text{maximize}} &&&\sum_{j=1}^m y_{j}\\ {\text{subject to}} &&&\sum_{i\in S_j^+}x_i +\sum_{i\in S_j^-}(1-x_i)\ge y_j,&&1\le j\le m,\\ &&&x_{i}\in \{0,1\},&&1\le i\le n,\\ &&&y_{j}\in \{0,1\},&&1\le j\le m. \end{aligned}$

线性规划松弛:
将$\{0,1\}$改为$[0,1]$.
随机近似:

$\hat x_i=\begin{cases} 1 & \text{with probability }x_i^*,\\ 0 &\text{with probability }1-x_i^*. \end{cases}$

近似比分析:

$OPT\le OPT_{LP}=\sum_{j=1}^m y_j^*$ $\begin{aligned} \Pr[C_j \text{is satisfied}]&=1-\prod_{i\in S_j^+}(1-x_i^*)\prod_{i\in S_j^-}x_i^*\\ &\ge 1-(1-y_j^*/k)^k\\ &\ge [1-(1-1/k)^k]y_j^* \qquad \text{ (convexity)}\\ &\ge (1-1/e)y_j^* \end{aligned}$ $\mathbb E[\text{number of satisfied clauses}]\ge (1-1/e)\sum_{j=1}^my_j^*\ge (1-1/e)\cdot OPT$

两个算法结合

随机解满足$m_1$子句, 随机近似LP松弛满足$m_2$子句, 选择$\max\{m_1,m_2\}$,
分析:

$\mathbb E[\max\{m_1,m_2\}]\ge \mathbb E[\frac{m_1+m_2}{2}]\ge \frac{3}{4}OPT$

近似比$3/4$(因为$1-2^{-k}$和$1-(1-1/k)^k$中总有一个$\ge 3/4$)