Arora Algorithm 4 k-light Tours

发表于 2021-08-16 更新于 2022-06-18 分类于 TSP ， PTAS 阅读次数：

Arora算法, k-light环游.

我们的目标是求$g^{-1}(\text{OPT}_g)$, 然而直接求$\text{OPT}_g$是困难的, 因此我们便试图求其近似$\text{OPT}_{m,a,b}$, 然而, 求$\text{OPT}_{m,a,b}$依然是困难的, 因此要根据问题要求对所求的环游进一步做出限制.

一条portal-respecting环游是k-light若其穿过正方形的每条边都不超过$k$次.

在本节, 我们会证明若$k=\frac{24}{\epsilon}+4$, 则至少有$\frac{1}{2}$的概率使得求得的最短k-light环游有至多$(1+\epsilon)|\text{OPT}_g|$的费用. 为此, 要先证明两个引理.

引理3 (Patching Lemma) 令$S$为一条长为$s$的线段, $\pi$为穿过$S$至少三次的圈. 则我们可以在所有$S$和$\pi$除去其中一个交点之外的所有交点处割断该圈, 然后以总长至多为$3s$的若干线段重新连接成圈$\pi^\prime$, 使得$S$穿过该圈至多两次.

证明

==仅给出总长至多为$6s$的证明.== 思路为构造$4-$正则图, 然后在该图上找欧拉闭迹.

设$\pi$与$S$相交$t$次, 交点依次为$M_1,M_2, \ldots,M_t$, 使得圈依次分为路$P_1,P_2,\ldots,P_t$. 令$M^\prime_i$, $M^{\prime\prime}_i$ ($i=1,2,\ldots,t$)为$M_1,M_2, \ldots,M_t$的分别在$S$两边的复制. 设$2j$为不大于$t$的最大偶数.

令$J$为满足以下条件的线段集合

经过$M_1,M_2,\ldots,M_t$的TSP环游;

$M_1,M_2,\ldots,M_{2j}$的最小费用完美匹配.

注意到这些边都在$S$上, 且长度和不超过$3s$. 令$J^\prime$和$J^{\prime\prime}$为分别加在$S$两侧的$J$的复制

若$t=2j+1$, 则加边$M^\prime_{2j+1}M^{\prime\prime}_{2j+1}$; 若$t=2j+2$, 则加边$M^\prime_{2j+1}M^{\prime\prime}_{2j+1}$和$M^\prime_{2j+2}M^{\prime\prime}_{2j+2}$. 注意到这些边的长度都为$0$.

上述新加的边和$P_1,P_2,\ldots,P_{2j}$构成了一个以$\{M^\prime_{1},M^\prime_2,\ldots,M^\prime_t\}\cup\{M^{\prime\prime}_{1},M^{\prime\prime}_2,\ldots,M^{\prime\prime}_t\}$为顶点的$4-$正则图. 则该图的欧拉闭迹就是我们要求的圈$\pi^\prime$. 其长度至多比$\pi$大$3s$, 且与$S$至多相交两次.

下图是证明过程的一个例子.

引理4 对于扰动和放缩后的实例, 设$\pi$为一条环游, $l$为任一条其穿越过的网格线, 令$t(\pi,l)$为$\pi$穿过$l$的次数, 则有 \[ \sum_{l: \text { vertical }} t(\pi, l)+\sum_{l: \text { horizontal }} t(\pi, l) \leq 2 \operatorname{cost}(\pi). \]

证明

考虑下图所示环游$\pi$, 其中$ag$和$ch$表示该环游的最大垂直和水平跨度.

观察下图可知 \[ \sum\limits_{l:\text{ vertical}}t(\pi,l)-1\le ag < \sum\limits_{l:\text{ vertical}}t(\pi,l)+1, \] 同理可得 \[ \sum\limits_{l:\text{ horizontal}}t(\pi,l)-1\le ch < \sum\limits_{l:\text{ horizontal}}t(\pi,l)+1. \]

由三角不等式得 \[ ag<ab<\text{cost}(\pi_{adb})=\text{cost}(\pi_{ad})+\text{cost}(\pi_{bd}), \]

\[ ch<cd<\text{cost}(\pi_{cbd})=\text{cost}(\pi_{bc})+\text{cost}(\pi_{bd}). \]

因此 \[ \begin{aligned} \sum_{l: \text { vertical }} t(\pi, l)+\sum_{l: \text { horizontal }} t(\pi, l) &\leq ag+ch+2 \\ &< \text{cost}(\pi_{ad})+\text{cost}(\pi_{bd})+\text{cost}(\pi_{bc})+\text{cost}(\pi_{bd})=2 \\ &= \text{cost}(\pi)+\text{cost}(\pi_{bd})-\text{cost}(\pi_{ac})+2 \\ \end{aligned} \] 同理有 \[ \sum_{l: \text { vertical }} t(\pi, l)+\sum_{l: \text { horizontal }} t(\pi, l) <\text{cost}(\pi)+\text{cost}(\pi_{ac})-\text{cost}(\pi_{bd})+2 \] 不妨$\text{cost}(\pi_{bd})\ge\text{cost}(\pi_{ac})$, 则有 \[ \begin{aligned} \sum_{l: \text { vertical }} t(\pi, l)+\sum_{l: \text { horizontal }} t(\pi, l) &<\text{cost}(\pi)+2+\max\{\text{cost}(\pi_{bd})-\text{cost}(\pi_{ac}),\text{cost}(\pi_{ac})-\text{cost}(\pi_{bd})\} \\ &=\text{cost}(\pi)+2+\text{cost}(\pi_{bd})-\text{cost}(\pi_{ac}) \\ &\le 2\text{cost}(\pi) \end{aligned} \]

下面我们要证明, 对于扰动和缩放后的实例, 令$k\ge \frac{24}{\epsilon}+5$, 任何一条最优环游$\pi$ (等同于上文的$|\text{OPT}|_g$), 都可以转化为一条k-light环游, 而且不增加额外的费用. 这可以使得我们使用动态规划求解中的状态数量大大减少.

对于任一条垂直的网格线$l$ (对于水平的网格线的分析过程类似), 设其level为$i$. 则其与$2^{i+1}$个level为$i+1$的正方形接触, 并将自身分割为$2^{i+1}$份长为$\frac{L}{2^{i+1}}$的segment. 对$j>i$, 网格线$l$也同样和$2^j$个level为$j$的正方形接触. 我们称$l$的位于level为$j$正方形部分的线段为level j segment. 我们的最终目标是: 对于每个level i segment, 将其被环游穿越的数量控制在$k$次或以下. 具体方法如下.

令$s=k-4$. 定义segment为overloaded若环游穿越其至少$s+1$次. 按level递增的顺序, 依次对每个level的overloaded segment使用Patching Lemma, 直至没有overloaded segment. 使用Patching Lemma产生的新的路都经过portal, 因此会产生一些迂回.下图展示了一个$L=8$的例子.

首先分析其费用.

设$X_{l,j}(b)$为表示在上述过程中待处理的垂直的overloaded level j segments的数量. 其只由$b$决定. ==(为什么和$a$没有关系?)==

对任意$b$, 有 $$ \[\begin{aligned} t(\pi,l) &= \#\{\text{not }\textit{overloaded }\text{crossing}\} + \#\{\textit{overloaded }\text{crossing}\} \\ &= \#\{\text{not }\textit{overloaded }\text{crossing}\} + \sum\limits_{j\ge0}\#\{\textit{overloaded }\text{crossing at }\textit{level }j\text{segment}\} \\ &= \#\{\text{not }\textit{overloaded }\text{crossing}\} + \sum\limits_{j\ge0}\sum\limits_{X_{l,j}(b)}\bigg(2+\#\{\text{eliminated crossings of a }\textit{level }j\textit{ segment}\}\bigg) \\ &\ge \#\{\text{not }\textit{overloaded }\text{crossing}\} + \sum\limits_{j\ge0}\sum\limits_{X_{l,j}(b)}(s+1) \\ &\ge (s+1)\sum\limits_{j\ge0}X_{l,j}(b) \end{aligned}\]

\[ 因此 \] X_{l,j}(b). $$ ==(Gutin, 217 (2007)给出的上界是$\frac{t(\pi,l)}{s-1}$)==

由于level i segment的长度是$\frac{L}{2^{j}}$, 由Patching Lemma, 处理垂直的overloaded segment所需添加的路的费用不超过 \[ \sum_{j \geq 1} X_{l, j}(b) \cdot \frac{3 L}{2^{j}}. \] (由于level为$0$的正方形为enclosing box, 因此在上式略去)

考虑此过程对环游的整体影响 \[ \text { Increase in tour cost when } l \text { has level } i \leq \sum_{j>i+1} X_{l, j}(b) \cdot \frac{3 L}{2^{j}}. \] 对任意$b$, 有 \[ \begin{aligned} \mathrm{E}_a[\text{charge to }l\text{ when horizontal shift if }a] &=\sum_{i \geq 1} \frac{2^{i+1}}{L} \cdot(\text { charge to } l \text { when its level is } i)\\ &\leq \sum_{i \geq 1} \frac{2^{i+1}}{L} \cdot \sum_{j \geq i+1} X_{l, j}(b) \cdot \frac{3 L}{2^{j}}\\ &=3 \cdot \sum_{j \geq 2} \frac{X_{l, j}(b)}{2^{j}} \cdot \sum_{1\leq i \leq j-1} 2^{i+1}\\ &=12 \cdot \sum_{j \geq 2} \frac{X_{l, j}(b)}{2^{j}} \cdot\left(2^{j-1}-1\right)\\ &\leq 6 \cdot \sum_{j \geq 2} X_{l, j}(b)\\ &\leq \frac{6 t(\pi, l)}{s+1} \end{aligned} \] ==(与Gutin, 218 (2007)的证明略有不同)==

结合引理4及$s\ge\frac{24}{\epsilon}+1$得 \[ \begin{aligned} \mathrm{E}_a[\text{charge to }l\text{ when horizontal shift if }a] & \leq \frac{6 t(\pi, l)}{s+1} \\ & \leq 12\frac{\text{cost}(\pi)}{s+1} \\ & \leq \frac{\epsilon}{2}\text{cost}(\pi) \end{aligned} \] ==(这里的$\pi$是上文中的$|\text{OPT}_g|$, 因此证明到这里还不能说明此操作后得到的解经过逆扰动后是原问题的一个$(1+\epsilon)$近似)==

最后分析其是否是k-light.

上述算法的停止准则不足以说明得到的解是k-light, 因为很可能在结束垂直overloaded segment的处理后, 在处理水平overloaded segment时, 又产生了新的垂直的overloaded segment. 由Patching Lemma容易说明这种情况至多会新增$4$次穿越. 而$s+4=k$, 则证明了得到的解是k-light. 详细过程不过多赘述, 见Gutin, 219 (2007).