Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight.
Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm.
Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.
more »
« less
Online Spanners in Metric Spaces
Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight.
Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm.
Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.
more »
« less
 Award ID(s):
 1800734
 NSFPAR ID:
 10433191
 Date Published:
 Journal Name:
 30th Annual European Symposium on Algorithms (ESA 2022)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in ℝ^d. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on ε > 0 and d ∈ ℕ of the minimum lightness of a (1+ε)spanner, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner (1+ε)spanners of lightness O(ε^{1}logΔ) in the plane, where Δ ≥ Ω(√n) is the spread of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness Õ(ε^{(d+1)/2}) in dimensions d ≥ 3. Recently, Bhore and Tóth (2020) established a lower bound of Ω(ε^{d/2}) for the lightness of Steiner (1+ε)spanners in ℝ^d, for d ≥ 2. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions d ≥ 2. In this work, we show that for every finite set of points in the plane and every ε > 0, there exists a Euclidean Steiner (1+ε)spanner of lightness O(ε^{1}); this matches the lower bound for d = 2. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.more » « less

null (Ed.)Lightness and sparsity are two natural parameters for Euclidean (1+ε)spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in dspace admits an (1+ε)spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)spanner. They gave upper bounds of Õ(ε^{(d+1)/2}) for the minimum lightness in dimensions d ≥ 3, and Õ(ε^{(d1))/2}) for the minimum sparsity in dspace for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)spanners of lightness O(ε^{1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{d/2}) for the lightness and Ω(ε^{(d1)/2}) for the sparsity of such spanners in Euclidean dspace for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)spanners of lightness O(ε^{1}log n) for n points in Euclidean plane.more » « less

Grandoni, Fabrizio ; Herman, Grzegorz ; Sanders, Peter (Ed.)Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, some of the remaining vertices of a reliable spanner may no longer admit the spanner property, but this collateral damage is bounded by a fraction of the size of the attack. It is known that Ω(nlog n) edges are needed to achieve this strong property, where n is the number of vertices in the network, even in one dimension. Constructions of reliable geometric (1+ε)spanners, for n points in ℝ^d, are known, where the resulting graph has 𝒪(n log n log log⁶n) edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical  replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip list like construction. This results in a 1spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in ℝ^d with 𝒪(n log log²n log log log n) edges.more » « less

Given a set S of n points in the plane and a parameter ε>0, a Euclidean (1+ε) spanner is a geometric graph G=(S,E) that contains a path of weight at most (1+ε)∥pq∥2 for all p,q∈S . We show that the minimum weight of a Euclidean (1+ε)spanner for n points in the unit square [0,1]2 is O(ε−3/2n−−√), and this bound is the best possible. The upper bound is based on a new spanner algorithm that sparsifies Yaographs. It improves upon the baseline O(ε−2n−−√), obtained by combining a tight bound for the weight of an MST and a tight bound for the lightness of Euclidean (1+ε)spanners, which is the ratio of the spanner weight to the weight of the MST. The result generalizes to dspace for all d∈N : The minimum weight of a Euclidean (1+ε)spanner for n points in the unit cube [0,1]d is Od(ε(1−d2)/dn(d−1)/d), and this bound is the best possible. For the n×n section of the integer lattice, we show that the minimum weight of a Euclidean (1+ε)spanner is between Ω(ε−3/4n2) and O(ε−1log(ε−1)n2). These bounds become Ω(ε−3/4n−−√) and O(ε−1log(ε−1)n−−√) when scaled to a grid of n points in [0,1]2. .more » « less