Approximating Euclidean Shallow-Light Trees

Abstract

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 $(\hat{I}\pm ,{\hat{I}}^2)$-SLT of $G$ w.r.t. $s\in V$ is a spanning tree of $G$ with root-stretch $\hat{I}\pm$ (preserving all distances between $s$ and the other vertices up to a factor of $\hat{I}\pm$) and lightness ${\hat{I}}^2$ (its weight is at most ${\hat{I}}^2$ 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 $\hat{I}\mu >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 \mathrm{polylog}(1/\hat{I}\mu ))$ time, a non-Steiner (resp., Steiner) tree with root-stretch $1+O(\hat{I}\mu \log \hat{I}{\mu }^{-1})$ and weight at most $O({\mathrm{opt}}_{\hat{I}}\mu \cdot {\log }^2\hat{I}{\mu }^{-1})$ (resp., $O({\mathrm{opt}}_{\hat{I}}\mu \cdot \log \hat{I}{\mu }^{-1})$), where ${\mathrm{opt}}_{\hat{I}}\mu$ denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch $1+\hat{I}\mu$.

The abstract has been truncated to satisfy the arXiv character limit