给定 n 节点图 G=(V,E)，每条边有权重 w:E\to\mathbb{Z}{\geq 0} 和长度 l:E\to\mathbb{Z}{\geq 0}，根节点 r\in V 和长度上限 h\in\mathbb{Z}_{\geq 0}。目标是找到一棵生成树，使得权重之和最小且任意节点到根的长度不超过 h。我们在平面图上设计了多项式时间算法：对任意常数 \epsilon>0，算法在保证每个节点到根的距离不超过 (1+\epsilon)h 的同时，输出权重至多 O(\log^{1+\epsilon} n) 倍的近似解。核心技术是构造了新的长度受限平面分割器，这些分割器本身可能有独立价值。算法同样适用于长度受限 Steiner 树，并证明自然线性规划的整数间隙上界为 O(\log^3 n / \epsilon)，同样带有 (1+\epsilon) 的长度松弛。相反，我们证明在一般图上，即使要求所有节点到根的距离不超过 2h，也不可能在标准复杂性假设下得到 O(\log^{2-\epsilon} n) 的近似比。于是平面图与一般图在该问题的可近似性上出现了明显分离。
点评