Arora Algorithm 3 Portal-Respecting Tours

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

Arora算法, 关于门的环游.

我们已知$g^{-1}(\text{OPT}_g)$是$\text{OPT}$的一个$(1+\epsilon)$近似, 也给出了$g^{-1}$ (逆扰动) 的方法, 但$\text{OPT}_g$仍然是难求的. 因此我们避开直接求解$\text{OPT}_g$, 而是求解其近似解, 为此要给出一个重要概念: 门 (portal).

Portal是网格线上的一些特殊点. 令$m$为以$2$为底的幂. 在每条level为$i$的线上设置$2^{i+1}m$个均匀分布的portal. 在每个正方形的四角也分别设置portal. 观察得, 每条边上至多有$m+2$个portal, 每个正方形上至多有$4m+4$个portal ==(这个上界是否可以缩小为$3m+4$尚存疑问)==. 一个$L=8,m=2$的例子如下图所示 (省略了一些正方形得四角位置得portal, 以及enclosing box上得所有portal).

关于门的 (portal-respecting) 环游定义为只在portal处穿过网格线的环游, 其由参数$m,a,b$共同决定. 记最短的portal-respecting环游为$\text{OPT}_{m,a,b}$, 其值为$|\text{OPT}_{m,a,b}|$. 下图给出了一个$m=2$时的例子 (这个例子的顶点都在格点上, 太特殊了).

由于欧氏空间满足三角不等式, 最短的portal-respecting环游$\text{OPT}_{m,a,b}$访问同一portal的次数至多为两次, 超过三次的环游都可通过下图展示的方式改进. 因此$\text{OPT}_{m,a,b}$至多刺穿同一正方形$8m$次. ==(为何不是$8m+8$尚存疑问)==

下面讨论$m$的选取, 以及解$\text{OPT}_{m,a,b}$的质量.

对任意的$u,v\in \mathbb{R}^2$, 定义portal-respecting距离为$u$和$v$间只在portal处穿过网格线的最短距离, 其由参数$a,b$决定, 记为$d_{a,b}(u,v)$. 记$u$和$v$的直线距离为$d(u,v)$, 显然有$d_{a,b}(u,v)\ge d(u,v)$.

引理 1 当$a,b$为$\{1,2,\ldots,l\}$中随机选取时, $\mathrm{E}[d_{m,a,b}(u,v)-d(u,v)]\le \frac{2\log L}{m} d(u,v)$.

证明

考虑长为$d(u,v)$的线段 (直的线段) 与网格相交的次数. Gutin, 214 (2007)指出其相交次数至多不超过$2d(u,v)$, ==这个上界对线段长度应是有限制的== (因为短的线段与网格相交的效率更高, 考虑与网格线呈45°的线段, 设其长为$n\sqrt{2}+\epsilon$, 其中$\epsilon$为任意小的正数, 则其至多与网格线相交$2(n+1)$次, 此时当且仅当$n\ge\sqrt{2}+1$时才满足相交次数至多不超过$2(n\sqrt{2}+\epsilon)$次). 以两倍线段长为自变量, 最大格点相交次数为因变量作图如下, 可以发现, 当线段长至少为$6$时能满足其与格点相交次数至多不超过两倍的最短距离, 这在算法中应是容易满足的.

采用如下方式构造$u$和$v$间的portal-respecting最短路: 沿着$uv$, 没穿越一次网格线, 则绕到距离交点最近的portal穿越, ==(如何证明这种方法能产生最短路)== 下图是一个例子. 观察得到该最短路能够按穿越网格的次数进行分解, 如下图虚线红框所示.

我们便只需要考虑与网格线相交一次增加的费用. 思路为使用迂回路 (上图橙色实线) 利用三角不等式放缩到portal的间距, 来给出其上界. 一个简单的例子如下图所示.

则有 $$ \[\begin{aligned} d_{m,a,b}(u,v)-d(u,v) &= \min \{ua+av,ub+bv\} - uv \\ &\le \min \{uo+oa+ao+ov,uo+ob+bo+ov\} \\ &= \min\{oa,ob\} \\ &\le oa+ob \\ &= ab \end{aligned}\]
$$ 由上可知穿越一次网格线, 费用的增加量至多为一直线上两portal间的最大距离.
根据portal的定义, 每条线上至少有$2^{i+1}m$个portal, 故其两两间距至多为$\frac{L}{2^{i+1}m}$, 其中$i$为线的level. 因此 $$ \[\begin{aligned} \mathrm{E}[\text{穿越网格线的费用增加量}] &= \sum\limits_{\text{level i}}\operatorname{Pr}[\text {线位于}\textit{level }i]\cdot (\text{穿越该线的费用增加量}) \\ &\le \sum\limits_{\text{level i}}\operatorname{Pr}[\text {线位于}\textit{level }i]\cdot (\text{该直线上两}\textit{portal}\text{间的最大距离}) \\ &= \sum\limits_{\text{level i}}\frac{2^{i+1}}{L}\cdot\frac{L}{2^{i+1}m} \\ &= \sum\limits_{i=0}^{\log L-1}\frac{1}{m} \\ &= \frac{\log L}{m} \end{aligned}\]
$$

由于$uv$与网格相交的次数至多为$2d(u,v)$次, 因此总的穿越网格线的费用增加量的期望不超过$\frac{2\log L}{m} d(u,v)$, 即 \[ \mathrm{E}[d_{m,a,b}(u,v)-d(u,v)]\le \frac{2\log L}{m} d(u,v). \]

推论2 当$a,b$为$\{1,2,\ldots,l\}$中随机选取时, $\mathrm{E}[|\text{OPT}_{m,a,b}|-|\text{OPT}_g|]\le \frac{2\log L}{m} |\text{OPT}_g|$.

由期望的线性性质直接得证.

回顾$\text{OPT}_g$为扰动后的最优解的顶点排列, 上式说明了通过求解portal-respecting环游$\text{OPT}_{m,a,b}$来近似$\text{OPT}_g$的效果可以由$L$和$m$的选取来控制. 记$E=\mathrm{E}[|\text{OPT}_{m,a,b}|-|\text{OPT}|]$, 由Markov不等式可知 $$ \[\begin{aligned} \operatorname{Pr}[|\text{OPT}_{m,a,b}|-|\text{OPT}_g|\le\frac{4\log L}{m}|\text{OPT}_g|] &\ge\operatorname{Pr}[|\text{OPT}_{m,a,b}|-|\text{OPT}_g|\le2E] \\ &=1-\operatorname{Pr}[|\text{OPT}_{m,a,b}|-|\text{OPT}_g|\ge2E] \\ &\ge1-\frac{E}{2E} \quad(\text{Markov's inequality})\\ &=\frac{1}{2} \end{aligned}\] \[ 因此下式以至少$\frac{1}{2}$的概率成立 \] \[\begin{aligned} |g^{-1}(\text{OPT}_{m,a,b})| & \le |\text{OPT}_{m,a,b}|+ \sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}} \\ & \le (1+\frac{4\log L}{m})|\text{OPT}_g|+ \sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}} \\ & \le (1+\frac{4\log L}{m})|g(\text{OPT})|+\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}} \\ & \le (1+\frac{4\log L}{m})|\text{OPT}|+2\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}} \\ \end{aligned}\]

\[ \begin{aligned} g^{-1}(\text{OPT}_{m,a,b})\text{是}\text{OPT}\text{的}(1+\epsilon)\text{近似} & \Longleftarrow (1+\frac{4\log L}{m})|\text{OPT}|+2\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}}\le|\text{OPT}|(1+\epsilon) \\ & \Longleftrightarrow |\text{OPT}|(\epsilon-\frac{4\log L}{m})- \frac{2\sqrt{2}}{\sqrt{n}}\epsilon d \ge 0\\ \end{aligned} \]

已知$d=\frac{2n^{1.5}}{\epsilon}$.

由$2d\le|\text{OPT}|\le nd$, 得$|\text{OPT}|\ge 2d=\frac{4n^{1.5}}{\epsilon}$.

由$\frac{l}{2}< d\le \sqrt{2} l$ (对于第一个不等号, 考虑在一直线上的$d=4+\epsilon$的一串点, 其中$\epsilon$任意小, 由于$l$为以$2$为底的幂, 又要包含所有顶点, 所以应取$l=8$), 及$\epsilon>n^{-\frac{1}{3}}$, 得$L=2l<4d=\frac{8n^{1.5}}{\epsilon}<8n^{\frac{11}{6}}$.

令$m\ge \frac{8 \log n}{\epsilon}$. ==(Gutin, 214 (2007))给出$m$的下界是$m\ge \frac{4 \log n}{\epsilon}$, 但我没证出来)==

将上述四个式子带入得 $$ \[\begin{aligned} |\text{OPT}|(\epsilon-\frac{4\log L}{m})- \frac{2\sqrt{2}}{\sqrt{n}}\epsilon d &\ge\frac{4n^{1.5}}{\epsilon}\bigg(\epsilon - \frac{4\log (8n^{\frac{11}{6}})\epsilon}{8\log n}\bigg)-4\sqrt{2}n \\ &=4n^{1.5}\bigg(\frac{1}{12}-\frac{\sqrt{2}}{\log n} \bigg)-4\sqrt{2}n \\ &\ge0 \quad (\text{当}n\ge203418) \end{aligned}\]

$$ 由上可知在$n\ge203418$, 选取$m\ge \frac{8 \log n}{\epsilon}$, $a,b$为$\{1,2,\ldots,l\}$中随机选取的情况下, 上述portal-specting环游$\text{OPT}_{m,a,b}$有至少$\frac{1}{2}$的概率是$\text{OPT}$的一个$(1+\epsilon)$近似.