PACT 07/08 叒访顶点覆盖 & 单机任务调度

Posted on 2020-07-12 Views:

用对偶规划解顶点覆盖

回顾一下，顶点覆盖问题的主线性规划（松弛后）是

$\begin{aligned} \text{minimize}\quad &\sum_{v\in V}w_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{maximize}\quad &\sum_{v\in E} y_e \\ \text{subject to}\quad &\sum_{v\in e} y_e \le w_v \quad \forall v \in V\\ &y_e \ge 0\quad \forall e\in E \end{aligned}$

我们在此设计一个通过解对偶规划来求得原问题解的近似算法。依赖于对偶规划的好处是：在分析过程中我们必须给 $\mathrm{OPT}$ 一个下界，而由对偶规划的定义，对偶规划的目标函数值就是一个非常好的下界，因此基于对偶规划的近似算法在分析上是比较便利的。

假设我们已经求得了对偶规划的最优解，如何以此确定原规划的变量取值呢？回忆我们在学对偶时学到的互补松弛条件

若主线性规划最优解中一变量非零，则其对偶规划中对应约束收紧。

其逆命题为

若对偶规划中对应约束收紧，则主规划中对应变量非零。

虽该命题未必正确，但给我们设计算法提供了思路。我们的算法就是：

求取对偶规划的最优解。
对于最优解中每一个紧约束，将其在主规划中对应的顶点加入顶点覆盖。

接下来我们分析一下这个算法：

引理：我们给出的顶点覆盖是可行的。

证明：不妨假设我们给出的顶点覆盖不合法，即有一条边 e=(u,v) 没有被覆盖到。那么由我们的算法可知 u,v 对应的对偶约束在对偶最优解中是松的，而既然如此为什么不增加 y_e 使其一收紧，同时增加目标函数的值呢？显然这和“我们求得对偶规划的最优解”是矛盾的。

定理：我们的算法是一个倍近似算法。

证明：假设我们算法给出的覆盖集为，则我们顶点覆盖的总代价就是 $\sum_{v\in C}w_v$ ，而由我们算法选取顶点的条件，有

$\begin{aligned} \sum_{v\in C}w_v &= \sum_{v \in C}\sum_{v\in e\in E} y_e \\ &= \sum_{e\in E} y_e |C\cap e| \\ &\le \sum_{e\in E} y_e \cdot 2 \\ &= 2 \cdot \mathrm{OPT}_{\text{dual}} \\ &\le 2 \cdot \mathrm{OPT} \end{aligned}$

（正如之前所说，对偶规划的目标函数给我们提供了 $\mathrm{OPT}$ 的一个极佳的下界）

得证。

（后记：其实对偶解的最优性在这里并没有用到，是不是每一组对偶规划的极大解都可以呢？）

单机任务调度

定义

输入：一台机器个任务，第个任务的发布时间是 r_i ，耗时 p_i 。

目标：设第个任务的完成时刻为 C_i ，要求制定一个非竞争性（non-preemptive）的任务调度方案，使得 $\sum_{i=1}^nC_i$ 最小。所谓非竞争性，是指一个任务一旦开始就不能被其他任务所打断，不能够一个任务做一会暂停再去做另一个任务，与其相对的成为竞争性调度。

思路与算法

我们不妨先考虑如果允许竞争性调度，我们应该怎么办呢？

一个显然的策略是不断选取剩余耗时最短的任务优先完成，这样其他任务等待的时间最少。

注意到，一个非竞争性的调度方案可以在允许竞争的情况下应用，而反之未必然。因此，若设 $C_i^{\text P}$ 为在最优竞争性调度中任务的结束时刻，那么就有

$\sum_{i=1}^n C^{\text P}_i \le \mathrm{OPT}$

一个竞争性的方案可以被转化为一个非竞争性的方案吗？这就是我们的算法：

求解在允许竞争的情况下的最优调度方案。
按照任务在竞争性最优调度中结束的顺序确定我们解当中各任务的执行顺序，并基于这个顺序给出我们非竞争性的调度方案。

分析

设 $C_i^{\text N}$ 为我们的非竞争性调度中任务的结束时刻，那我们方案的代价就是 $\sum_{i=1}^n C^{\text N}_i$ 。

接下来假设我们已经按照任务在竞争性最优调度当中结束的顺序给任务排了序。

注意到

$C^{\text N}_i \le \max_{1 \le k \le i} \{r_k\}+ \sum_{k=1}^i p_k$

这是显然的，因为不等式的右边描述了一种可行的调度方案：等前

个任务全部发布后再连续把它们做完，而我们的方案不会比这个可行方案差。

令任务为前个任务当中最晚发布的那个任务，即 $r_l = \max_{1\le k \le i}\{r_k\}$ 。因为我们是按照竞争性最优方案中任务结束的顺序调度的，因此 $C_i^{\text P} \ge C_l^{\text P}$ 。常识告诉我们 $C_l^{\text P} \ge r_l$ ，因此 $C_i^{\text P} \ge r_l$ 。而显然又有 $C_i^{\text P} \ge \sum_{k=1}^i p_k$ ，因此

$C^{\text N}_i \le \max_{1 \le k \le i} \{r_k\}+ \sum_{k=1}^i p_k \le C_i^{\text P} + C_i ^{\text P} = 2C_i^{\text P}$

因此

$\sum_{i=1}^n C^{\text N}_i \le 2\sum_{i=1}^n C^{\text P}_i \le 2\cdot \mathrm{OPT}$

所以我们的算法是一个

倍近似算法。

拓展：任务带权

我们现在对于这个问题进行拓展，每个任务都有一个权重 w_i ，我们要最小化 $\sum_{i=1}^nw_iC_i$ 。

对于这个问题，我们上面的思路就行不通了：我们上面的算法建立在可以最优求解竞争性调度的基础上，而可以证明，即使允许竞争，求解带权任务调度也是一个NP hard问题。

因此我们必须换一个思路，考虑给我们的问题放宽一下条件，再以这个松弛的问题为基础建立一个线性规划（LP-relaxation）。很容易就能想到如下的线性规划：

$\begin{aligned} \text{minimize}\quad &\sum_{i=1}^n w_iC_i \\ \text{subject to}\quad &C_i \ge r_i + p_i\quad \forall i=1,2,\cdots,n \\ &C_i \ge 0\quad \forall i=1,2,\cdots,n \end{aligned}$

可是这个线性规划一看就松到了一个扯淡的地步。是个人就知道这个规划的最优解就是

，我们完全不能够指望这个破规划给我们任何有意义的结果或指引我们进行算法设计。我们还要加点条件——多多少少要体现出任务的非竞争性吧？

于是就有了这个加强版的线性规划：

$\begin{aligned} \text{minimize}\quad &\sum_{i=1}^n w_iC_i \\ \text{subject to}\quad &C_i \ge r_i + p_i\quad \forall i=1,2,\cdots,n \\ & \sum_{i\in S}p_iC_i \le \frac{1}{2}p(S)^2 \quad \forall S\subseteq \{1,2,\cdots. m\}\\ &C_i \ge 0\quad \forall i=1,2,\cdots,n \end{aligned}$

其中 $p(S) = \sum_{i \in S} p_i$ 。

这个第二个约束是怎么一回事呢？考虑所有任务都在一开始就发布，然后任务时间无缝衔接的情况。此时一个任务的完成时间就等于之前所有任务耗时之和。为方便起见，不妨令 $S=\{p_1,p_2,p_3,\cdots,p_{|S|}\}$ ，于是有

$\begin{aligned} \sum_{i = 1}^{|S|} p_iC_i &= \sum_{i = 1}^{|S|} p_i\sum_{j=1}^i p_j \\ &= \sum_{i = 1}^{|S|} p_i^2 +\sum_{i = 1}^{|S|} p_i\sum_{j=1}^{i-1} p_j \\ &= \frac{1}{2}\left(\sum_{i = 1}^{|S|} p_i^2 + 2\sum_{i = 1}^{|S|} p_i\sum_{j=1}^{i-1} p_j\right) + \frac{1}{2}\sum_{i = 1}^{|S|} p_i^2 \\ &= \frac{1}{2}\left(\sum_{i = 1}^{|S|} p_i\right)^2+ \frac{1}{2}\sum_{i = 1}^{|S|} p_i^2 \\ &\ge \frac{1}{2}p(S)^2 \end{aligned}$

若嫌代数证明太不直观，则下图在几何上说明了这一点：

在实际的调度当中，几个任务未必无缝衔接，因此 $C_i \ge \sum_{j=1}^i p_j$ ，而我们的证明依然成立。因此对于可行的非竞争性调度，以上约束总是成立。虽反之不然，却也比一开始那个过于简陋的线性规划更多地刻画了“非竞争性”的特点。对于我们的算法来说，这个线性规划已经足够。我们的算法为：