PACT 07/06 线规舍入 + 背包问题

Posted on 2020-07-11 Views:

线性规划舍入（LP Rounding）

对于很多的 $\mathsf{NP}$ 问题，我们都可以写出一个对应的整数规划（IP），然而写成整数规划本身没有啥用，因为整数规划也是 $\mathsf{NP}$ 的。但是整数规划可以通过松弛转变为线性规划，后者是可以在多项式时间内求解的，这就给近似算法的设计提供了一个思路。

唯一的问题是，线性规划给出的解未必就是整数了（在例如网络流问题等特殊的问题下还是有可能的），因此我们需要在确保解的可行性的前提下对于线性规划的解进行舍入，这个技巧便成为LP rounding。

以带权顶点覆盖问题为例，其整数规划为

$\begin{aligned} \text{minimize}\quad &\sum_{v\in V}c_vx_v \\ \text{subject to}\quad &x_u+x_v\ge 1\quad \forall (u, v)\in E \\ &x_v \in \{0,1\}\quad \forall v\in V \end{aligned}$

表示

是否被选入覆盖集当中。

其松弛后的线性规划为

$\begin{aligned} \text{minimize}\quad &\sum_{v\in V}c_vx_v \\ \text{subject to}\quad &x_u+x_v\ge 1\quad \forall (u, v)\in E \\ &x_v \ge 0\quad \forall v\in V \end{aligned}$

显然这个线性规划在有的时候不会给出整数解，例如对于一个三角形，整数规划会给两个顶点的

赋

，而线性规划会给三个顶点赋 $\frac{1}{2}$ 。

于是就需要舍入。如何舍入？设线性规划最优解 $x_v^*\ge \frac{1}{2}$ 时，整数规划的解 $\hat x_v$ ，则

$\hat x_v = \begin{cases} 1,&x_v^*\ge \frac{1}{2} \\ 0,&x_v^*< \frac{1}{2} \end{cases}$

由于我们的约束 $x_u+x_v\ge 1$ ，

当中至少有一个 $\ge \frac{1}{2}$ ，因此这么舍入后的解依然是可行解。

注意到如果按照这么舍入， $\hat x_v \le 2x_v^*$ ，又注意到线性规划的最优解一定不大于原整数规划的最优解，即 $\mathrm{OPT}$ ：

$\sum_{v\in V}c_v\hat x_v \le \sum_{v\in V}2c_vx_v^* = 2\sum_{v\in V}c_vx_v^* \le 2\cdot\mathrm{OPT}$

因此我们的算法就是一个

倍近似算法。这个算法较之前极大匹配算法的优势在于其可以很好地处理点带权的情况。

背包问题

定义

输入：件物品，每一件物品有重量 w_i 和价值 p_i ，以及背包容量。

目标：在物品总重不超过背包容量的前提下使得打包的物品价值总和最大。

贪心算法

一个非常简单直接的想法是按照价重比（ $\frac{p_i}{w_i}$ ）贪心，但是这个贪心非常容易被卡掉，比如说有两个物品，第一件物品的重量为，价值为 $1+\varepsilon$ ，第二件物品的重量和价值都是，那按照价重比贪心我会先选第一件，然后之后就不能选第二件了，这个方案就很糟糕，而且和最优解的差距可以任意大。

但是有一个简单的小优化：假设物品是我们第一个因为放不下不选的物品，我们最后在贪心的方案和物品单件中择优输出，这个算法一下子就会好上很多——事实上这就是一个倍近似算法了。

证明：分两种情况。

贪心方案的总重 $> \frac{W}{2}$ 。因为我们是按照价重比贪心的，因此最优解的总价重比不会大于我们贪心方案的价重比，而贪心方案的重量至多是，因此此时我们贪心方案的总价值至少为最优方案的 $\frac{1}{2}$ 。
贪心方案的总重 $\le\frac{W}{2}$ 。装不下下一个，说明接下来的物品是重量 $>\frac{W}{2}$ 的大块头，令这个物品为。这样的大块头在任何打包方案当中都至多塞一个。此时最优解总价值不大于当前贪心解价值与之和（这个论断可以通过画图的方式进行证明，目前似乎还没有找到更有说服力的纯文字证明）。因为我们最后择优输出，因此我们最终方案的总价值至少是最优方案的 $\frac{1}{2}$ 。

动态规划

背包问题的动态规划是老生常谈的问题了，时间复杂度是 $\mathcal O(nW)$ ，看起来是多项式？其实不然，因为有关的信息只需要 $\mathcal O(\log W)$ 个比特存储，因此这个时间复杂度实际上是和输入长度成指数级的。

多项式时间近似方案（PTAS）

接下来我们提供背包问题的一个多项式时间近似方案（PTAS）。什么是PTAS？一个PTAS可以认为是一类基于参数 $\varepsilon$ 的算法，且参数为 $\varepsilon$ 的算法构成问题的 $(1+\varepsilon)$ 倍近似（对于最大化问题则可以是 $(1-\varepsilon)$ 倍近似）。算法的运行时间可以和 $\frac{1}{\varepsilon}$ 成指数级（因为在每一个算法当中， $\varepsilon$ 被视作常数），如果算法的运行时间和 $1 \over \varepsilon$ 成多项式级，则这个PTAS被称为完全多项式时间近似方案（FPTAS或FPAS）。

要设计这个算法，我们先从DP入手。考虑背包问题的如下DP：设 A(i, p) 是考虑前个物品，总价值为时的最小总重，则有如下转移：

$A(i, p) = \begin{cases} 0, &i=0 \text{ or }p=0 \\ A(i-1, p), &p<p_i \\ \min \{A(i-1,p),w_i+A(i-1,p-p_i)\}, &\text{otherwise} \end{cases}$

如果设所有物品的最大价值是

，那么显然总价值最多便是

，DP的时间复杂度就是 $\mathcal O(n^2P)$ 。我们主要担心的问题是

太大，要解决这个问题，我们把

缩小就行了。

因此我们的PTAS是：对于每件物品，对其价格等比例缩小舍入，新的价格为 $p_i'=\lfloor p_i / k\rfloor$ 。随后进行DP，并输出DP的最优解。设最优解为。

这样一来我们的总价格是多少呢？（定义 $p(\cdot)$ 表示集合的价格）。

$\begin{aligned} p(S) &= \sum_{i \in S} p_i \\ &\ge \sum_{i \in S} p_i'k \\ &= k\sum_{i \in S} p_i' \\ &\ge k\sum_{i \in \mathrm{OPT}} p_i' \\ &\ge k\sum_{i \in \mathrm{OPT}} \left(\frac{p_i}{k} - 1\right) \\ &= \sum_{i \in \mathrm{OPT}} p_i- k|\mathrm{OPT}| \\ &\ge \sum_{i \in \mathrm{OPT}} p_i - kn \end{aligned}$

第二个不等号处用到了DP的最优性。

若令 $k=\frac{\varepsilon P}{n}$ ，则有

$\begin{aligned} p(S) &\ge \sum_{i \in \mathrm{OPT}} p_i - kn \\ &= \sum_{i \in \mathrm{OPT}} p_i - \varepsilon P \\ &\ge p(\mathrm{OPT}) - \varepsilon p(\mathrm{OPT}) \\ &= (1-\varepsilon) p(\mathrm{OPT}) \end{aligned}$

第二个不等号处用到了 $p(\mathrm{OPT}) \ge P$ 。（此处我们忽略不可能装得下的物品）

因此这个算法确实是一个PTAS。这个算法的运行时间是多少呢？

$\mathcal{O} (n^2P) = \mathcal O \left(n^2 \frac{P}{k}\right) = \mathcal O\left(\frac{n^3}{\varepsilon}\right)$

可见这个算法其实不仅是一个PTAS，还是一个FPTAS。这个时间复杂度可以说是很优秀的了。