For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$, a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an $(α, β)$-SLT of $G$ w.r.t. $s \in V$ is a spanning tree of $G$ with root-stretch $α$ (preserving all distances between $s$ and the other vertices up to a factor of $α$) and lightness $β$ (its weight is at most $β$ times the weight of a minimum spanning tree of $G$). Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards this question by presenting two bicriteria approximation algorithms. For any $ε>0$, a set $P$ of $n$ points in constant-dimensional Euclidean space and a source $s\in P$, our first (respectively, second) algorithm returns, in $O(n \log n \cdot {\rm polylog}(1/ε))$ time, a non-Steiner (resp., Steiner) tree with root-stretch $1+O(ε\log ε^{-1})$ and weight at most $O(\mathrm{opt}_ε\cdot \log^2 ε^{-1})$ (resp., $O(\mathrm{opt}_ε\cdot \log ε^{-1})$), where $\mathrm{opt}_ε$ denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch $1+ε$.

翻译：对于一个带权图 $G = (V, E, w)$ 和一个指定的源顶点 $s \in V$，若一棵生成树能同时近似于关于源 $s$ 的最短路径树和最小生成树，则称为浅光树（SLT）。具体而言，图 $G$ 关于 $s \in V$ 的 $(α, β)$-SLT 是 $G$ 的一棵生成树，其根拉伸度为 $α$（即保留 $s$ 与其他顶点间所有距离至多放大 $α$ 倍），且轻量度为 $β$（其权重至多为 $G$ 的最小生成树权重的 $β$ 倍）。尽管已有大量关于 SLT 的研究，但关于是否存在更优近似算法这一基本问题至今尚未触及，且这在任何图族中均成立。本文通过提出两种双准则近似算法，首次向该问题迈出了非平凡的一步。对于任意 $ε>0$、常数维欧几里得空间中的 $n$ 个点集 $P$ 及源点 $s\in P$，我们的第一个（分别对应第二个）算法在 $O(n \log n \cdot {\rm polylog}(1/ε))$ 时间内返回一棵非 Steiner（分别对应 Steiner）树，其根拉伸度为 $1+O(ε\log ε^{-1})$，且权重至多为 $O(\mathrm{opt}_ε\cdot \log^2 ε^{-1})$（分别对应 $O(\mathrm{opt}_ε\cdot \log ε^{-1})$），其中 $\mathrm{opt}_ε$ 表示根拉伸度为 $1+ε$ 的非 Steiner（分别对应 Steiner）树的最小权重。