Search for: All records

Abstract: For a weighted graph G = (V, E, w) and a designated source vertex s ∈ 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 ∈ V is a spanning tree of G with root-stretch α (preserving all distances between s and all other vertices up to a factor of α) and lightness β (its weight is at most β times the weight of a minimum spanning tree of G). It was shown in the early 1990s that (1) for any graph, any source, and any ε > 0, there is a (1 + ε, O(1/ε))-SLT, and (2) there exist graphs for which β = Ω(1/ε) for any (1+ε,β)-SLT. The focus of this work is on SLTs in low-dimensional Euclidean spaces, which are of special interest for some applications of SLTs, in geometric network optimization problems. The aforementioned existential lower bound applies to Euclidean plane, as well. It was shown more than a decade ago that (1) by using Steiner points, one can reduce the lightness bound from O(1/ε) to O(√{1/ε}), and (2) there exist point sets in the plane for which β = Ω(√{1/ε}) for any Steiner (1+ε,β)-SLT. These tight existential bounds for the Euclidean case yield approximation factors of O(1/ε) and O(√{1/ε}) on the minimum weight of any non-Steiner and Steiner tree with root-stretch 1+ε, respectively. 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 resolving 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 ∈ P, our first (respectively, second) algorithm returns, in O(n log n ⋅ polylog(ε^{-1})) time, a non-Steiner (resp., Steiner) tree with root-stretch 1+O(ε log ε^{-1}) and weight at most O(opt_ε ⋅ log² ε^{-1}) (resp., O(opt_ε ⋅ log ε^{-1})), where opt_ε denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch 1+ε. 

In their seminal paper, Althöfer et al. (DCG 1993) introduced the greedy spanner and showed that, for any weighted planar graph 𝐺, the weight of the greedy (1 +𝜖)-spanner is at most (1+2/𝜖) ⋅w⁡(𝖬𝖲𝖳⁡(𝐺)), where w(𝖬𝖲𝖳⁡(𝐺)) is the weight of a minimum spanning tree MST⁡(𝐺) of 𝐺. This bound is optimal in an 𝑒⁢𝑥⁢𝑖⁢𝑠⁢𝑡⁢𝑒⁢𝑛⁢𝑡⁢𝑖⁢𝑎⁢𝑙 𝑠⁢𝑒⁢𝑛⁢𝑠⁢𝑒: there exist planar graphs 𝐺 for which any (1+𝜖)-spanner has a weight of at least (1+2/𝜖) ⋅𝑤⁡(MST⁡(𝐺)). However, as an 𝑎⁢𝑝⁢𝑝⁢𝑟⁢𝑜⁢𝑥⁢𝑖⁢𝑚⁢𝑎⁢𝑡⁢𝑖⁢𝑜⁢𝑛 𝑎⁢𝑙⁢𝑔⁡𝑜⁢𝑟⁢𝑖⁢𝑡⁢ℎ⁡𝑚, even for a 𝑏⁢𝑖⁢𝑐⁢𝑟⁢𝑖⁢𝑡⁢𝑒⁢𝑟⁢𝑖⁢𝑎 approximation, the weight approximation factor of the greedy spanner is essentially as large as the existential bound: There exist planar graphs 𝐺 for which the greedy (1 +𝑥⁢𝜖)-spanner (for any 1 ≤𝑥 =𝑂⁡(𝜖−1/2)) has a weight of Ω⁡(1/𝜖⋅𝑥2) ⋅w⁡(𝐺opt,𝜖), where 𝐺opt,𝜖 is a (1 +𝜖)-spanner of 𝐺 of minimum weight. Despite the flurry of works over the past three decades on approximation algorithms for spanners as well as on light(-weight) spanners, there is still no (possibly bicriteria) approximation algorithm for light spanners in weighted planar graphs that outperforms the existential bound. As our main contribution, we present a polynomial-time algorithm for constructing, in any weighted planar graph 𝐺, a (1 +𝜖 ⋅2𝑂⁡(log∗⁡1/𝜖))-spanner for 𝐺 of total weight 𝑂⁡(1) ⋅w⁡(𝐺opt,𝜖). To achieve this result, we develop a new technique, which we refer to as 𝑖⁢𝑡⁢𝑒⁢𝑟⁢𝑎⁢𝑡⁢𝑖⁢𝑣⁢𝑒 𝑝⁢𝑙⁢𝑎⁢𝑛⁢𝑎⁢𝑟 𝑝⁢𝑟⁢𝑢⁢𝑛⁢𝑖⁢𝑛⁢𝑔. It iteratively modifies a spanner; each iteration replaces a heavy set of edges by a light path, to substantially decrease the total weight of the spanner while only slightly increasing its stretch. We leverage planarity to prove a 𝑙⁢𝑎⁢𝑚⁢𝑖⁢𝑛⁢𝑎⁢𝑟 structural property of the edge set to be removed, which enables us to optimize the path to be inserted via dynamic programming. Our technique applies dynamic programming 𝑑⁢𝑖⁢𝑟⁢𝑒⁢𝑐⁢𝑡⁢𝑙⁢𝑦 𝑡⁢𝑜 𝑡⁢ℎ⁡𝑒 𝑖⁢𝑛⁢𝑝⁢𝑢⁢𝑡 𝑝⁢𝑙⁢𝑎⁢𝑛⁢𝑎⁢𝑟 𝑔⁡𝑟⁢𝑎⁢𝑝⁢ℎ, which significantly deviates from previous techniques used for network design problems in planar graphs, and might be of independent interest.