PACT 07/10 主对偶方法

Posted on Edited on Views:

什么是主对偶方法？

对于所有可以写成整数规划/线性规划形式的问题（不妨假设是最小化问题），由对偶定理可得，对偶最优解一定是\mathrm{OPT}的一个下界。

因此，对偶可行解也是\mathrm{OPT}的一个下界。

所谓的主对偶方法（Primal-dual Method），就是从一个对偶规划的可行解出发，不断优化这个对偶可行解，并在这个过程中利用对偶规划的特性指引我们求得原问题的解。

太抽象？

叕访顶点覆盖

（顶点覆盖问题属实牛逼嗷，那么多近似方法都可以用）

顶点覆盖问题的主线性规划是

\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}
显然，y_e=0就是一个平凡的对偶可行解。基于主对偶方法的思想，我们可以得到两个算法：

算法1

  1. 初始化y_e\gets0,C\gets \emptyset。
  2. 当还有一条边(u,v)没有被覆盖时，
    1. \varepsilon\gets \min\left\{w_u-\sum_{u\in e} y_e,w_v-\sum_{v\in e} y_e\right\}。
    2. y_e\gets y_e+\varepsilon（以上两步旨在尽可能增加y_e直至两端点中一个点对应的约束收紧）。
    3. 假设增加y_e之后u对应的约束收紧了，那么C\gets C\cup\{u\}。
    4. 同时删除所有与u邻接的边。
  3. 返回C。

（注意到，当w_u=1时，这个算法退化为我们最初学的极大匹配算法）

算法2

  1. 初始化y_e\gets0,C\gets \emptyset。
  2. 当C不是一个合法的顶点覆盖时，
    1. \varepsilon\gets \min_{v\in V} \left\{\frac{1}{\deg(v)}\sum_{v\in e}y_e\right\}
    2. 对于所有边e\in E，y_e\gets y_e+\varepsilon（以上两步旨在同时增加所有y_e直至有约束收紧）。
    3. 将所有紧约束对应的顶点加入C。
    4. 同时删去这些点和它们邻接的所有边。
  3. 返回C。

其实还有很多这样的寻找局部极大对偶可行解的方法，以上两个算法是最容易想到的。

分析

两个算法的分析是共通的：

\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}
以上步骤的第一步是因为我们加入覆盖集的所有顶点对应的约束都是紧的。

主对偶方法神奇的一点就在于：虽然我们在线性规划的指导下进行设计与分析，但是最后的算法却是一个完全不需要求解线性规划的纯粹的组合算法（Combinatorial Algorithm），因此非常优雅。

再探设施选址

回忆之前设施选址的线性规划。y_i表示设施i是否被选，x_{ij}表示用户j是否到设施i去：

\begin{aligned} \text{minimize}\quad &\sum_{i\in F}f_iy_i + \sum_{j\in D}\sum_{i \in F}c_{ij}x_{ij} \\ \text{subject to}\quad &\sum_{i\in F}x_{ij} \ge 1 \quad \forall j\in D \\ &y_i - x_{ij} \ge 0 \quad \forall i\in F, j\in D \\ &x_{ij} \ge 0 \quad \forall i\in F, j\in D \\ &y_i \ge 0 \quad \forall i \in F \end{aligned}
其对偶为
\begin{aligned} \text{maximize}\quad &\sum_{j \in D}\alpha_j \\ \text{subject to}\quad &\alpha_j - \beta_{ij} \le c_{ij}\quad \forall i \in F, j\in D \\ &\sum_{j\in D}\beta_{ij} \le f_i\quad \forall i\in F \end{aligned}

以下将对偶规划中第一行的约束称为“第一类约束”，第二行的约束称为“第二类约束”。

算法

我们设计一个基于主对偶方法的近似算法：

  1. 初始化\alpha_j\gets 0,\beta_{ij}\gets 0（平凡的对偶可行解）。
  2. 以相同的速率同时增加的值\alpha_j。
  3. 当对于某些i,j出现\alpha_j=c_{ij}时，为了能够在不违反第一类约束的前提下让\alpha_j继续增加，我们开始同步增加\beta_{ij}的值。
  4. 随着一些\beta_{ij}值的增加某些第二类约束也会收紧，此时暂时开放该约束对应的设施。因为此时对应的\beta_{ij}不能再增加了，那些\alpha_j也自然不会再增加了，我们就此将这些\alpha_j的值冻结起来（其余的\alpha_j可以继续增加）。
  5. 不断重复以上步骤直至所有的\alpha_j都被冻结了。
  6. 按照第4步开放的先后顺序处理所有暂时开放的设施，
    1. 永久开放该设施，
    2. 并将所有和该设施共享一个“紧顾客”（tight client，指和设施对应约束是紧的顾客，这里实在是不怎么好翻，具体的解释参看下面的感性认识和接下来的分析），即那些两边的\beta都大于0的顾客的暂时开放的设施关闭（移出队列）。

听听这是人话吗？感性理解一下以上算法（也有助于接下来的分析）：

  1. \alpha_j可以理解为每个顾客为了得到服务愿意付出的代价，一开始所有人都想白嫖。
  2. 显然如果大家都想白嫖的话没有一个人会得到服务，因此大家一起提升这个愿意付出的代价。
  3. 当\alpha_j=c_{ij}也就是某个顾客发现自己愿意支付的价位内出现了设施的时候他就很高兴。但是这个设施没开，所以顾客决定给这个设施的开放分摊成本（增加\beta_{ij}），但是这样也不是个事，万一不远处有个不需要他付钱或者只需要分摊很少开张费用的设施呢？所以\alpha_j的增长也不能落下。
  4. 当有第二类约束收紧，即几个顾客终于凑够了钱让这个设施开放，那么这个设施就暂时开张了。这几个用户很满足，就准备去这个设施了，所以他们的\alpha_j不增加了。
  5. 不断重复以上步骤直至满足所有顾客的需求。
  6. 按照第4步开放的先后顺序处理暂时开张的设施，
    1. 永久开张，
    2. 如果去这个设施的顾客里有人给其他设施也分摊成本了，那把那些设施全部关掉。

（如果我把上面变量的名字换一下，把“第一类约束”，“第二类约束”也换个名字，那么从上面的算法当中你根本看不到线性规划的痕迹，这就是一个听着很有道理实际上近似比也有保证的组合算法。这就是主对偶方法的优雅之处。）

分析

我们不妨称那些为最后永久开放的设施垫付开张成本的顾客为“幸运顾客”，形式上地来说，一个顾客j为幸运顾客当且仅当最后永久开张的设施中有一处设施i使得\alpha_j-\beta_{ij}=c_{ij},\beta_{ij}>0，也就是说顾客j和设施i之间在对偶规划对应的约束是紧的——这也是上面tight client的本意。

相对地我们称不是幸运顾客的那些顾客“倒霉顾客”，说他们倒霉是因为他们明明给某些设施分摊了开张成本，也都准备好去那里了，结果这个设施在最后关掉了。

不妨设最后决定开张的设施为F'，幸运顾客的集合为L。j \to i表示顾客j到设施i的约束是紧的（也就是顾客j给设施i分摊了成本）。注意由于我们算法最后一步的清理操作，每个幸运顾客只可能垫付一个F中设施的成本，那么设施的开放费用和幸运顾客的服务成本可以一起表示为：

\begin{aligned} &\quad\,\sum_{i\in F'}f_i+\sum_{j\in L} \sum_{\substack{i\in F'\\ j\to i}} c_{ij}\\ &= \sum_{i \in F'}\sum_{\substack{j\in L\\ j\to i}} \beta _{ij}+\sum_{j\in L} \sum_{\substack{i\in F'\\ j\to i}} \left(\alpha_j - \beta_{ij}\right) \\ &=\sum_{j \in L} \alpha_{j} \end{aligned}
我们接下来分析倒霉顾客的情况。

假设有一个倒霉顾客k，他分摊了设施b的开张成本并最终让设施b暂时开张（同时假设b是他分摊成本的设施中最先开张的——也就是\alpha_k恰在b开张后被冻结）。但是比b早开张的设施a中有一个幸运顾客j也为b分摊了成本，导致最后清理的时候b被关闭了。不妨假设k最后只能去a。注意到由三角不等式，

\begin{aligned} c_{ak} &\le c_{aj} + c_{bj} +c_{bk} \\ &\le (\alpha_j-\beta_{aj}) + (\alpha_j - \beta_{bj}) + (\alpha_{k}-\beta_{bk}) \\ &\le \alpha_j+\alpha_j + \alpha_k \\ &\le 3\alpha_k \end{aligned}
最后一步之所以成立，是因为a开张后\alpha_j必然冻结，\alpha_k停止增长要等到b开张后。而a比b先开张，因此\alpha_k \ge \alpha_j。我们在上面假设k最后去了a，其实如果最后k去了比a还近的那自然他的服务成本更低了。

因此倒霉顾客的服务成本\le \sum_{k\in D\setminus L} \alpha_k。

结合上述的分析，我们可以得到我们的总成本：

\begin{aligned} \text{total cost} &\le \sum_{j\in L} \alpha_j + \sum_{k\in D\setminus L} 3\alpha_k \\ &\le 3\sum_{j\in D}\alpha_j \\ &\le 3\cdot\mathrm{OPT} \end{aligned}
也就是说，我们证明了我们这个算法的近似比为3。

为什么最后一步要清理一些暂时开张的设施？

为什么我们算法的最后一步要清理暂时开张的设施呢？为什么不能一些用户分摊够开张费用就让这个设施永久开张下去呢？

考虑如下的一个实例：

有n个设施，其中f_1=n+1且f_i=n+2\quad\forall i =2,3,\cdots,n。

有2n个顾客。前n名顾客到所有设施的距离都是1。对于后面的n名顾客，第n+i名顾客只和设施i的距离为1，和其余设施的距离都为3。易证这样的边权满足三角不等式。

现在考察我们算法的运行情况：

  • t=0，初始化。
  • t=1，所有的\alpha_j=1，每名顾客开始为至少一个设施分摊成本了。
  • t=2，对于任何一个设施都有n+1名顾客为其人均分摊了1的开张成本，而注意到f_1=n+1，因此设施1开张了，相应地，前n名顾客和第n+1名顾客的\alpha_j被冻结。其余的n-1名顾客继续为对应的设施分摊费用。
  • t=3，剩下的n-1家设施全部开张。

如果没有最后的清理步骤，那么我们的算法会开放所有的设施。光是开放设施的代价就有n+1+(n-1)(n+2)=\Omega(n^2)。而只开一家设施的代价是O(n)的。因此最后的清理步骤非常重要！