启发式 RSMA 算法
本文收录于 EDA 论文选读，系 Sailesh K. Rao, P. Sadayappan, Frank K. Hwang, Peter W. Shor 所作论文 The Rectilinear Steiner Arborescence Problem 之阅读笔记。
TL;DR
基本概念
在 EDA 中，最优化一个 net 的延迟自然地引出曼哈顿平面上的最短路 steiner tree 问题。学术上将这个问题命名做 Rectilinear Steiner Minimal Arborescence (RSMA) 问题，其形式定义如下：
定义 1（RSMA）. 一个欧式空间第一象限中的一个 RSMA 乃是一个以原点为根，且经过另外 $n$ 个第一象限中的点（称作汇点）的外向有根树。其中每条边的起点 $x_u$ 和终点 $x_v$ 之间必须满足 $x_u \prec x_v$，此处 $\prec$ 为二维空间上的标准二维偏序。
兹建立一些关于此问题的直觉。
引理 1. 在任意一个 RSMA $A$ 中，若 $u, v$ 的父亲相同，则有其父亲 $z = \min(u, v)$，这里 $\min$ 表示对横纵坐标分别取最小值。
证明.
假设其反面，那么在 $\min(u, v)$ 处新增一个点 $z’$，有 $l(u, z’) + l(v, z’) + l(z, z’) < l(u, z) + l(v, z)$，与原树为 RSMA 矛盾。$\blacksquare$
将 $G(N)$ 定义做 $n$ 个汇点及原点所在横纵坐标织成的网格，则类似于 RSMT 的结论，我们有:
定理 2. 存在仅使用 $G(N)$ 中的点的 RSMA。
证明.
任取一个 RSMA $A$，按照到原点的距离由远及近归纳。注意任意两个点 $u, v$ 的父亲为 $z = \min(u, v)$，所以边 $(u, z), (v, z)$ 必为网格边，$z$ 必为网格格点。$\blacksquare$
似乎还不知道 RSMA 问题是否是 $\mathbf{NP}\text{-hard}$ 的。至少在某些特例上，其能在多项式时间内解决。
定理 3. 若给定的 $n$ 个汇点构成偏序集 $(\mathbb{R}^2, \prec)$ 上的反链，则原问题可以在 $O(n^3)$ 时间内解决。
证明.
区间 DP。$\blacksquare$
$\mathbb{R}^2$ 上有一类特殊的反链，为 $L_n : x + y = n$ 在第一象限（含坐标轴正方向）内的 $n + 1$ 个整点，简便起见将其记作 $D_n$。则容易想象这些点的 RSMA 应当连成线段树状，更严谨地可以考虑手动计算上述区间 DP，不难验证若 $n = 2^{\alpha} + \beta$，其中 $0\leq \beta < 2^\alpha$，则其 RSMA 总边长为 $n\alpha + 2\beta$。
现在考虑分析一些粗略地 RSMA 解的大小的界。有两个显而易见的方向：
- 众所周知最小生成树和最小斯坦纳树之间存在一个近似比，这个比例在最短路树和 RSMA 之间是否存在？
- RSMA 的大小与最小生成树的大小能够有多接近？
很遗憾，对于前者答案是不存在的。因为只需要考虑汇点集合 $D_n$，有
$$
\frac{w(\mathrm{SPT}(D_n))}{w(\mathrm{RSMA}(D_n))} = \Omega\left(\frac{n}{\log n}\right)
$$
而对于后者，我们在 上一篇文章 的引理 2 中给出的算法给出了一个上界（其实是紧的，最坏情况依旧是由 $D_n$ 给出）：
$$
\max_{S : |S| = n} \frac{w(\mathrm{RSMA}(S))}{w(\mathrm{RSMT}(S))} = O(\log n) \qquad {\color{orange} \text{In fact, $\Theta(\log n)$}}
$$
一种启发式算法
注意，一棵 RSMA 可以看作迭代地每次选择两个点 $u, v$，将其替换做 $\min(u, v)$ 而成。其代价为
$$
\lVert u\rVert + \lVert v\rVert - 2\lVert\min(u, v)\rVert
$$
涉及优化的部分仅有 $\lVert \min(u, v)\rVert$，由此自然引出一种启发式算法，即每次直接选最大化 $\lVert \min(u, v)\rVert$ 的两个点将其合并。
首先思考如何实现该算法。显然，只需实现一个斜向的扫描线（$x + y = k$，$k$ 从大到小），用一个平衡树维护当前扫描线上方的全部点。注意可能使得 $\lVert\min(u, v)\rVert$ 最大化的点对惟有横坐标相邻者（这也解释了我们为何需要用平衡树维护，这是为了查询前驱后继），因此只需要用可删堆来维护这些点对将产生的 steiner node。这样时间复杂度为 $O(n\log n)$。
兹证明该启发式算法对 RSMA 的近似比为 $2$，即对于任意的点集 $N$ 有此算法生成的树形图 $A$ 的权重满足
$$
\frac{w(A)}{w(\mathrm{RSMA}(N))} \leq 2
$$
为证明此结论，我们首先转换计算 $w(A)$ 的方法。注意到
$$
w(A) = \int_0^\infty \sqrt 2|L_x \cap A|\mathrm{d}x
$$
定义 $\mathrm{MC}(N, z)$ 表示在 $L_z$ 上取最少的点，使得对于任意一个 $N$ 中的点，都存在一个取出的点在其左下方。依该定义立即有对于任意的 $x$，
$$
|L_x \cap \mathrm{RSMA}(N)| \geq \mathrm{MC}(\{p\in N, \lVert p\rVert\geq x\}, x)
$$
我们将证明 $L_x\cap A \leq 2\mathrm{MC}(\{p\in N, \lVert p\rVert\geq x\}, x)$。
断言 1. 对任意该启发式算法生成的树 $A$ 的每一个节点 $p$，有以下两个集合上均存在至少一个汇点，且该汇点与 $p$ 之间存在路径：
$$
h_p := \{ (x, y_p) : x \geq x_p \}, \quad v_p = \{ (x_p, y) : y\geq y_p \}
$$
证明.
归纳即可。$\blacksquare$
断言 2. 该算法生成的树 $A$ 中不存在两条边相交。
证明.
同样归纳即可。$\blacksquare$
将算法扫描线运行至 $L_k$ 时，BST 中的点集记作 $W_k$。显然 $W_k$ 一定是 $(\mathbb{R}^2, \prec)$ 上的一个反链，且对于任意的 $p, q\in W_k$，有 $\lVert\min(p, q)\rVert < k$。这自然地推出 $\mathrm{MC}(W_k, k) = |W_k|$。进而只需讨论 $W_k$ 的覆盖集和 $\{u\in N : \lVert u\rVert\geq k\}$ 的覆盖集之间的关系。
断言 3. 对于任意的 $k$，对于任意的 $p, q\in W_k$ 满足 $x_p < x_q$（这也蕴含 $y_p > y_q$），以下集合上必存在至少一个汇点 $s$：
$$
\{(x, y_p) : x_p\leq x \leq x_q\} \cup \{(x_q, y) : y_q \leq y \leq y_p\}
$$
证明.
由断言 1 可以知道存在汇点 $p’$ 和 $p$ 有水平方向的连边，存在汇点 $q’$ 和 $q$ 有垂直方向的连边。若他们都不在上述集合之内，则 $A$ 中有两条边相交于 $(x_q, y_p)$，与断言 2 矛盾。$\blacksquare$
注意到覆盖了 $s$ 的点必然也能覆盖 $p, q$ 之一。因此欲覆盖全部的 $s$，至少将覆盖 $W_k$ 的一半，这自然导出
$$
|L_k \cup A| \leq |W_k| = \mathrm{MC}(W_k, k) \leq 2\mathrm{MC}(\{u\in N : \lVert u\rVert\geq k\}, k) \leq 2|L_k\cup \mathrm{RSMA}(N)|
$$
积分可得近似比确实是 $2$。