SALT Algorithm

Posted on Edited on In ,

本文收录于 EDA 论文选读，系 Gengjie Chen, Peishan Tu, Evangeline F. Y. Young 所作 ICCAD’17 的论文 SALT: Provably Good Routing Topology by a Novel Steiner Shallow-Light Tree Algorithm 之阅读笔记。

TL;DR

本文首先引述了参考文献 [1]，提出了一个 Steiner SLT 问题的 $(1 + 2\varepsilon, 4 + 2\lceil\log 2 / \varepsilon\rceil)$ 的 bound。

然后在得到了这个 bound 的情况下，选择相信 heuristics，把 FLUTE 算法和 CT Heuristics 拼起来得到了求 Rectilinear Steiner SLT 的算法。

基本定义 & 直觉

本文解决的核心问题是 Shallow Light Tree 问题。

定义 1（$(\alpha, \beta)$-SLT）. 带权图 $G = (V, E, w)$、配上根节点 $r$ 的一个 $(\alpha, \beta)$-SLT 是其一棵生成树 $T$，其中

  1. 对于任意的点 $v$，都有 $d_T(r, v) \leq \alpha d_G(r, v)$；
  2. 该树的权重 $w(T) \leq w(\mathrm{MST}(G))$。

直观地，将 $\alpha$ 称作 shallowness，将 $\beta$ 称作 lightness。

对于此问题的基本直觉是，$\alpha$ 和 $\beta$ 之间存在一个 trade-off，两侧的极端情况分别由最小生成树和最短路树给出。

当然在 EDA 当中，我们通常需要求 Manhattan 距离度量下的 Steiner Tree。对于一般的图 $G(V, E, w)$，其上方的最短路诱导出度量空间 $M_G$。这时，可以将图 $G$ 上的一个 Steiner Tree 定义做 $T = (V, E’, w’)$，其中 $T$ 诱导的度量空间 $M_T$ 支配 $M_G$（i.e. $\forall u, v, d_T(u, v)\geq d_G(u, v)$）。显然，这样的定义和习见的 Steiner Tree 并不相符——未必存在 $T$ 到原来度量空间的一个嵌入。但是，可以证明在 Manhattan 距离度量下，这样的嵌入是存在的。

Remark. 这个定义其实更像之前程设学的 Spanner。

对于 Steiner Tree 情形下的 SLT，只须将定义 1 中一切生成树修改做 Steiner Tree。

ES Algorithm

ES 算法是用于求解生成树情形下的 SLT 的 ABP 算法在 Steiner Tree 情形下的拓展。对于任意的 $\varepsilon$，它可以给出近似比为 $(1 + 2\varepsilon, 4 + 2\lceil \log(2/\varepsilon)\rceil)$ 的解。

该算法的流程为：

Algorithm 1（Ekkin, Solomon）.

  1. 令 $T_M\leftarrow \mathrm{MST}(G)$，$P$ 为 $T_M$ 的一个 dfs 序；
  2. 定义断点集合 $\mathcal{B}\leftarrow \varnothing$，上一个断点 $b\leftarrow r$；
  3. For $v = P_1, P_2, …, P_n$ do
  4. $\quad$ If $d_P(b, v) > \varepsilon \cdot d_G(r, v)$ do
  5. $\quad\quad$ $b\leftarrow v, \mathcal{B}\leftarrow \mathcal{B}\cup{v}$；
  6. $T_{\mathcal{B}} \leftarrow$ $G[\mathcal{B}\cup{r}]$ 上的最短路 steiner tree；
  7. $T\leftarrow$ $T_M\cup T_{\mathcal{B}}$ 上的最短路生成树。

为了阐释这里的近似比和启发后面的算法，我们有必要知道这里的最短路 Steiner Tree 是如何构造和分析的（尽管原文献直接引用了 [1]）。为此，我们证明下面的引理：

引理 1. 令 $G = (V, E, w)$ 是一个 $n$ 个点图，其上最短路诱导出度量 $M_G$，$r$ 是一个指定的根节点。令 $H$ 是度量空间 $M$ 上的一条从 $r$ 开始的哈密尔顿路径。则存在一个 $O(n^2)$ 的算法根据此哈密尔顿路径构造一棵二叉树 $T = (V’, E’, w’)$，满足：

  1. $T$ 以 $r$ 为根，$V$ 中除 $r$ 外的点充当 $T$ 的叶子，且度量 $M_T$ 支配 $M_G$；
  2. $T$ 中 $r$ 到叶子 $v$ 的路径长度恰为 $t$ 的最短路。
  3. $w’(T) \leq \log n\cdot w(H) + w(\mathrm{MST}(G))$。

证明.

我们首先给出这个算法。该算法将建立 $H[2, n]$ 上的线段树，然后给每条边赋一个非负权值，然后将线段树的根和 $r$ 连接并赋非负权值。兹记 $x$ 的左右儿子为 $L(x), R(x)$，对应边的权值为 $w_L(x), w_R(x)$；为了求出满足条件的权值，我们将自底向上地递推出这些量：

  1. $\rho(x)$：最短路的冗余量，即对于 $x$ 子树中的任意一个叶子 $v$ 都有 $d_G(r, v) - d_T(x, v) = \rho(x)$；辅以 $\delta(x) = \rho(L(x)) - \rho(R(x))$；

  2. $\Delta(x_L, x_R)$：距离的差额，其中 $x_L, x_R$ 分别为 $x$ 的左右子树中的叶子：

    $$
    \Delta(x_L, x_R) := d_G(x_L, x_R) - d_T(x_L, L(x)) - d_T(x_R, R(x))
    $$

    辅以子树内该距离差额的最大值

    $$
    \Delta(x) := \max\{\Delta(x_L, x_R)\}
    $$

最后由线段树的根 $r’$ 向 $r$ 连接的边之权值应为 $\rho(r’)$

为对齐权值及支配度量，惟需满足以下条件：

$$
\begin{cases}
w_L(x) - \rho(L(x)) = w_R(x) - \rho(R(x)) \\
w_L(x) + w_R(x) \geq \Delta(x)
\end{cases}
$$

出于保证构造出最短路 steiner tree 之需要，我们需要尽量节约最短路的冗余量。因此，给 $w_L(x)$ 和 $w_R(x)$ 的赋值应为

$$
\begin{cases}
w_L(x) = \frac{\Delta(x) + \delta(x)}{2}, w_R(x) = \frac{\Delta(x) - \delta(x)}{2}, & \text{if $\Delta(x) \geq |\delta(x)|$,} \\
w_L(x) = \max(\delta(x), 0), w_R(x) = \max(-\delta(x), 0), & \text{otherwise}
\end{cases}
$$

分析此算法的正确性，需要验证：

度量 $M_T$ 支配度量 $M_G$，$T$ 上根到叶子的距离恰为最短路

根据构造，显然成立。

$T$ 的边权必非负

只需验证 $\rho(r’)\geq 0$。为此，我们归纳验证对于一切线段树中的点 $x$ 都有 $\rho(x) \geq 0$。

对于叶子，结论显然成立。而对于非叶子节点 $x$，可注意到惟须考虑 $\Delta(x) \geq |\delta(x)|$ 的情形，因为另外一种情形连接了边权为 $0$ 的边，从而 $\rho(x)$ 将直接继承 $\rho(L(x))$ 和 $\rho(R(x))$ 中的一者。此时不妨设 $\rho(L(x)) \geq \rho(R(x))$。此时有

$$
\begin{aligned}
\rho(x) &= \rho(L(x)) - \frac{\Delta(x) + \rho(L(x)) - \rho(R(x))}{2} \\
&= \frac 12\left(\rho(L(x)) + \rho(R(x)) - \Delta(x)\right) \\
&=\frac{1}{2}\left(\min_{x_L, x_R}\left( d_G(r, x_L) + d_G(r, x_R) - d_G(x_L, x_R) \right)\right) \\
&\geq 0
\end{aligned}
$$

$T$ 的总边权不超过 $\log n\cdot w(H) + w(\mathrm{MST}(G))$

首先有

$$
w((r, r’)) = \rho(r’) \leq \max_x(d_G(r, x)) \leq \max_{x}d_{\mathrm{MST}(G)}(r, x) \leq w(\mathrm{MST}(G))
$$

然后我们只需要放缩 $w_L(x) + w_R(x)$。兹断言：

断言 1. $w_L(x) + w_R(x)$ 不超过子树内所有叶子节点构成的 $H$ 的子段的长度 $\mathcal{W}(l_x, r_x)$（此处 $\mathcal{W}(l, r)$ 表示 $H[l:r]$ 的长度）。

证明. 当 $\Delta(x) \geq |\delta(x)|$ 时，有

$$
w_L(x) + w_R(x) = \Delta(x) \leq d_G({x_L}, x_R) \leq \mathcal{W}
$$

否则

$$
\begin{aligned}
w_L(x) + w_R(x) &= \rho(L(x)) - \rho(R(x)) \\
&= d_G(r, x_L) - d_G(r, x_R) - d_T(L(x), x_L) + d_T(R(x), x_R) \\
&\leq d_G(x_L, x_R) + d_T(R(x), x_R)
\end{aligned}
$$

其中 $x_L, x_R$ 在子树里任取。此后只需要仔细证明一下存在一个 $x_R$ 使得 $d_T(R(x), x_R) \leq \mathcal{W}(x_R, r_{R(x)})$，形式化为如下断言：

断言. 对于树上任意一个点 $x$，存在子树中的点 $v$ 使得 $d_T(x, v)\leq \mathcal{W}(v, r_x)$。

证明. 方法仍是施归纳于该二叉树，若连了边权为 $0$ 的边，那么可以直接在两个子树之一（对应边权为 $0$ 的那个子树）中找到满足条件的点；否则取使 $\Delta(x_L, x_R)$ 取最大值的 $x_L, x_R$，有

$$
d_T(x, x_L) = w_L(x) + d_{T}(L(x), x_L) \leq \Delta(x) + d_T(L(x), x_L) \leq d_G(x_L, x_R) \leq \mathcal{W}(x_L, r_{x})
$$

$x_L$ 即为满足条件的点。

断言 1 直接推出线段树的边权和不超过 $\log n \cdot W(H)$。因而 $\log n\cdot w(H) + w(\mathrm{MST}(G))$。

明所欲证。$\blacksquare$

将引理 1 中所述算法用作求最短路 steiner tree 的算法，即得到当参数取 $\varepsilon$ 时，首先可以看到算法得到的树的 shallowness 为 $1 + 2\varepsilon$：考虑 $x$，其上一个断点为 $b$，

$$
\begin{aligned}
d_T(r, x) &\leq d_T(b, x) + d_T(b, r) \\
&\leq d_T(b, x) + \varepsilon d_G(r, v) \\
&= d_G(b, x) + \varepsilon d_G(r, v) \\
&\leq d_G(r, v) + d_G(r, x) + \varepsilon d_G(r, v) \\
&\leq (1 + 2\varepsilon)\cdot d_G(r, v)
\end{aligned}
$$

但是算法对最小 Steiner Tree 的近似比就非常 Tricky 了。因为如果直接引用引理证明中的 bound，可以发现给一张边权都是 $1$ 便可将 $\mathcal{B}$ 卡到 $n - 1$。然而，关于 $T$ 的大小实际上另有如下关于边权的 bound（这你妈是怎么想到的？？？）

引理 2. 给定正数 $\xi, \eta$，若哈密顿路径 $H$ 上所有点到 $r$ 的距离之和满足

$$
\sum_{i=2}^n d_G(r, H_i) \leq \xi \cdot \eta
$$

则有

$$
w(T) \leq \eta + \lceil\log(\xi)\rceil\cdot w(H) + w(\mathrm{MST}(G))
$$

证明.

若 $\lceil\log\xi\rceil \geq \log n$，则结论显然成立。不妨设 $\lceil\log\xi\rceil \geq \log n - 1$。

注意到定义 $W_i$ 表示线段树自下而上第 $i$ 层的边权之和，则

$$
\sum_{i = 2} d_G(v, H_i) = \sum_{i=1}^{\log n} 2^{\log n - i} W_i
$$

我们此前已经证明了 $W_i \leq w(H)$。当 $i \geq \log n - \lceil \log \xi \rceil$ 时，有

$$
\sum_{i=\log n - \lceil\log \xi \rceil + 1}^{\log n} \leq \lceil\log \xi\rceil\cdot w(H)
$$

而当 $i$ 较小时有

$$
\begin{aligned}
\xi\cdot \eta &\geq \sum_{i=1}^{\log n - \lceil\log \xi \rceil} 2^{\log n - i} W_i \\
&\geq \sum_{i=1}^{\log n - \lceil\log \xi \rceil} 2^{\log n - \log n + \lceil\log \xi\rceil} W_i \\
&\geq \xi \cdot\left(\sum_{i=1}^{\log n - \lceil\log \xi \rceil} W_i\right)
\end{aligned}
$$

这蕴含

$$
\sum_{i=1}^{\log n - \lceil\log \xi \rceil} W_i \leq \eta
$$

综上明所欲证。$\blacksquare$

此处因为 $H$ 取的是树的 dfs 序，其长度顶多是 $2w(\mathrm{MST}(G))$。令注意根据断点的选择方法，

$$
\sum_{i\in \mathcal{B}} \varepsilon d(r, i) \leq w(H) = 2\cdot w(\mathrm{MST}(G))
$$

取 $\xi = \frac 2\varepsilon, \eta = w(\mathrm{MST}(G))$ 立即得到

$$
w(T) \leq (2 + \lceil\log 2 / \varepsilon\rceil)\cdot w(\mathrm{MST}(G)) \leq (4 + 2\lceil\log 2 / \varepsilon\rceil)\cdot w(\mathrm{SMT}(G))
$$

这里用到了在任意的度量空间上都有 $\mathrm{MST}$ 是最小斯坦纳树的 $2$-近似。这表明算法生成的树的 lightness 至多为 $(4 + 2\lceil\log \varepsilon/2\rceil)$。

SALT Algorithm

他加了几个意义不明的改进，比如说

  1. 直接在树上松弛求断点，而不是在 Hamilton 路径上做这件事；
  2. 建线段树的时候，自底向上地将当前所有子树树根配对使得每次边权将增加最少（找一个环上的完美匹配）。

当然，直觉上来说这些都有改进，比如说你取环上的完美匹配，似乎至少可以让增加的权值不超过 Hamilton 环长度的一半。

然后用这个来证明 bound，但是有些非常 confusing 的地方，比如说：

  1. ES 算法的 lightness 是和 steiner tree 比的，这篇文章的 lightness 是和 MST 比的，凭什么宣称自己改进了近似比的 bound 到原来的两倍？
  2. 取完美匹配对 bound 的影响应该是把 $\log 2/\varepsilon$ 变成 $\log 1/\varepsilon$，那可能确实改进了，但是只在 log 因子上面。

现在我们已经把 bound 证出来了，那么为了实现一个 practical 的 Rectilinear Steiner SLT，我们选择相信 bound 和启发式算法：

  1. 把第一步的 MST 改成 FLUTE；
  2. 把第二步的建线段树改成 CL Heuristics；
  3. 最后还可以做一些后处理，比如说翻转 L 形边，提升 U 形的底边等。

效果非常好。

参考文献

  1. M. Elkin and S. Solomon, “Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones,” 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA, 2011, pp. 373-382, doi: 10.1109/FOCS.2011.18.