Arora Algorithm 1 Pertubation and Rescale

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

Arora算法, 扰动和比例调节.

令\(\epsilon > n^{-\frac{1}{3}}\), 设任意两点间的最大距离为\(d\). 设原问题的最优解为一顶点排列, 记为\(\text{OPT}\), 如下图红虚线所示, 设其长为\(|\text{OPT}|\), 易知\(2d\le|\text{OPT}|\le nd\), 同时对所有顶点的缩放不影响解的最优性.

扰动和缩放的具体步骤如下:

在该实例所在平面铺上间距为\(\frac{\epsilon d}{n^{1.5}}\)的正方形网格线;
定义\(g: v \in V \mapsto v_{g} \in \text { grid closest to } v\), 将\(g\)作用于顶点集合\(V\), 即将每个顶点移至距其最近的格点 (此时原问题的顶点可能在移动后重合于一个格点), 设在移动后的问题中的最优解为\(\text{OPT}_g\), 如下图红实线所示;
将上述格点最优解\(\text{OPT}_g\)修剪为原问题的最优解, 记为\(g^{-1}(\text{OPT}_g)\). (下图例子中\(|g^{-1}(\text{OPT}_g)|=|\text{OPT}|\), 但一般来说前者更大)

下估计\(|g^{-1}(\text{OPT}_g)|\)与\(|\text{OPT}|\)的差距, 观察得每个顶点移动距离的上界为\(\frac{\sqrt{2}}{2}\cdot\frac{\epsilon d}{n^{1.5}}\) (等号在顶点恰处于网格中心时取到), 任意边长度缩短或身长至多\(\sqrt{2}\cdot\frac{\epsilon d}{n^{1.5}}\) (考虑以原始边的两顶点为圆心, 顶点移动距离上界为半径作两圆, 观察顶点分别在两圆内所构成边的长度).

对任一可行解序列\(\pi=(i_1i_2\ldots i_n)\), \(i_1,i_2,\ldots,i_n\in\{1,2,.\ldots,n\}\)为顶点序号的一种排列. 设\(T=\big(v_{\pi(1)},v_{\pi(2)},\ldots,v_{\pi(n)}\big)\)为其对应的顶点排列, 其中\(v_{\pi(i)\in V}\), \(i=1,2,\ldots,n\). 设\(g(T)=T=\bigg(g(v_{\pi(1)}),g(v_{\pi(2)}),\ldots,g(v_{\pi(n)})\bigg)\)为该可行解在扰动后对应的顶点排列.

因为一个可行解由\(n\)条边构成, 因此扰动前后环游长度的变化至多为\(\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}}\), 即\(|T|-\sqrt{2}\cdot\frac{n\epsilon d}{\sqrt{n}}\le g(T)\le |T|+\sqrt{2}\cdot\frac{n\epsilon d}{\sqrt{n}}\). 将原问题最优解带入, 则有 \[ g(\text{OPT})\le |\text{OPT}|+\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}}. \] 回顾\(\text{OPT}_g\)为扰动后的最优解的顶点排列 , 而\(g(\text{OPT})\)为原问题最优解扰动后的顶点排列, 两问题的顶点集合是一样的, 但两个排列可能是不同的 (下图给出了一个单位网格的例子, 说明\(\text{OPT}\)在扰动后的值大大增加了), 因此 \[ |\text{OPT}_g|\le|g(\text{OPT})|. \]

综合上述两式则有 \[ |\text{OPT}_g|\le|g(\text{OPT})|\le |\text{OPT}|+\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}}. \] 上式给出了扰动后问题最优值\(|\text{OPT}_g|\)和原问题最优值\(|\text{OPT}|\)的差距, 但两问题顶点集不同, 我们的解应得到的解应是基于原问题顶点集的. 换句话说, 我们要对\(\text{OPT}_g\)进行修剪 (逆扰动), 得到解\(g^{-1}(\text{OPT}_g)\), 此即一个原问题的可行解.

\(g^{-1}(\text{OPT}_g)\)不是唯一确定的. 下图给出了单位网格下的例子, 原问题中的四个不同顶点在扰动后重合为了同一顶点, 其中蓝实线为\(\text{OPT}_g\)的一部分, 红虚线为某一\(g^{-1}(\text{OPT}_g)\)的一部分.

下面给出唯一确定\(g^{-1}(\text{OPT}_g)\)的一种方式: 对扰动至同一格点的原问题中的顶点排序, 然后在\(\text{OPT}_g\)到达该格点时, 依据此顺序依次连接原问题中的顶点. 在这种方式下, 多出的费用由两部分构成: 两点间的新增连接费用, 以及边在扰动作用下可能增加的费用, 无论是哪种情况, 其上界均为\(\sqrt{2}\cdot\frac{\epsilon d}{n^{1.5}}\). 而对于有\(n\)个顶点的实例, 增加费用的情况至多出现\(n\)次, 由此得到\(g^{-1}(\text{OPT}_g)\)关于\(\text{OPT}_g\)的一个费用上界, 即 \[ |g^{-1}(\text{OPT}_g)|\le |\text{OPT}_g|+\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}}. \]

由上述两式可知 \[ \begin{aligned} |g^{-1}(\text{OPT}_g)| & \le |\text{OPT}_g|+ \sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}} \\ & \le |g(\text{OPT})|+\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}} \\ & \le |\text{OPT}|+2\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}} \\ \end{aligned} \] 在给定实例大小\(n\)和\(\epsilon > n^{-\frac{1}{3}}\)的情况下, 上式告诉我们该解\(g^{-1}(\text{OPT}_g)\)的近似比完全是由图像缩放后顶点间最大距离\(d\)决定的. 因此我们要对原实例进行缩放 (等价于选择一个新的顶点间最大距离\(d\)), 使得其足够小到带入上式能够是一个\((1+\epsilon)\)近似, 又足够大到满足之后算法运行的要求 (因为之后算法在分割正方形时的停止准则为分割得到单位正方形, 若过小则分割层数过少, 算法执行后得到得解误差大).

为了达到上述目的, 考虑在原问题扰动后, 两点间的最小距离, 观察得该距离至少为网格宽度, 也即\(\frac{\epsilon d}{n^{1.5}}\). 我们令原问题所有顶点及网格线同时从\(\frac{\epsilon d}{n^{1.5}}\)放缩到\(2\), 此时的顶点间最大距离为\(d=\frac{2n^{1.5}}{\epsilon}\), 下分析如此选择的原因. \[ \begin{aligned} g^{-1}(\text{OPT}_g)\text{是}\text{OPT}\text{的}(1+\epsilon)\text{近似} & \Longleftarrow |\text{OPT}|+2\sqrt{2}\cdot\frac{\epsilon d}{\sqrt{n}}\le|\text{OPT}|(1+\epsilon) \\ & \Longleftrightarrow d=\frac{2n^{1.5}}{\epsilon}\le\frac{\sqrt{2n}}{4}|\text{OPT}| \\ & \Longleftrightarrow \epsilon|\text{OPT}| - 4\sqrt{2} n > 0 \end{aligned} \] 由于\(2d\le|\text{OPT}|\le nd\), 因此\(|\text{OPT}|\ge 2d=\frac{4n^{1.5}}{\epsilon}\)我们有 \[ \begin{aligned} \epsilon|\text{OPT}| - 4\sqrt{2} n & > 4n^{1.5}-4\sqrt{2}n \\ & >0\quad(\text{当}n>2) \end{aligned} \] 由上可知, 当实例大小\(n\)足够大时, \(g^{-1}(\text{OPT}_g)\)是原问题解\(\text{OPT}\)的一个\(1+\epsilon\)近似.