Online Spanners in Metric Spaces

Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, Csaba D. Tóth

Abstract

This paper investigates the construction of efficient network topologies, known as $t$-spanners, in an online setting. In this model, points arrive sequentially, and edges must be added to maintain a stretch factor $t$ without the ability to remove existing connections. We present the first comprehensive algorithms for $(1+\epsilon)$-spanners across various metric spaces. Our findings include a competitive ratio in the Euclidean plane that bypasses traditional lightness lower bounds and an "Ordered Greedy" algorithm that achieves near-optimal sparsity in general metrics.

Introduction

In network design, a $t$-spanner is a subgraph where the shortest path between any two points is at most $t$ times their direct distance. Ideal spanners are both sparse (minimal edges) and light (minimal total weight). While offline construction is well-understood, many real-world applications—such as sensor networks and expanding cloud infrastructure—require an online approach. In the online model, points arrive one at a time, and the algorithm must maintain the stretch factor $t$ for all points seen so far by only adding edges. This paper addresses the challenge of minimizing sparsity and weight relative to an offline optimum.

Algorithmic Strategies

The authors propose distinct strategies tailored to specific metric spaces:

  • Euclidean $d$-space: The approach combines dynamic quadtrees for hierarchical clustering with a modified ordered Yao-graph. Upon the arrival of a new point, the algorithm evaluates different hierarchical levels and adds edges to nearby representatives in various angular cones, provided the edges do not exceed weight thresholds for their respective levels.
  • General Metric Spaces: The "Ordered Greedy" algorithm is employed. When a new point $v_i$ arrives, potential edges to previous points are sorted by weight. An edge is added only if the current graph does not already provide a path shorter than the stretch threshold $t$.
  • Ultrametrics: For spaces where distances satisfy the strong triangle inequality, the authors utilize $k$-Hierarchical Well-Separated Trees ($k$-HSTs) to maintain minimal weight.

As a theoretical study, these methods are validated through rigorous mathematical proofs using adversarial sequences rather than empirical datasets.

Theoretical Analysis and Key Insights

Bypassing Lightness

Traditionally, spanner weight is measured by "lightness"—the ratio of the spanner's weight to that of the Minimum Spanning Tree (MST). In the Euclidean plane, the best possible lightness is $\Omega(\epsilon^{-2})$. However, by analyzing the competitive ratio (comparing the online spanner directly to the optimal offline spanner), the authors achieve a bound of $\tilde{O}(\epsilon^{-3/2})$, effectively surpassing standard lightness-based limitations.

The Power of Ordering

The "Ordered Greedy" algorithm demonstrates that processing edges in a specific weight-based order as points arrive is sufficient to achieve near-optimal sparsity in general metrics, even without prior knowledge of the total number of points $n$.

Dimensionality Constraints

The paper identifies a "curse of dimensionality" in online network design. By proving a lower bound under the $L_1$ norm, the authors show that the competitive ratio must grow exponentially with the dimension $d$ as $\Omega(\epsilon^{-d})$.

Key Results

The following table summarizes the established upper and lower bounds for online spanners across different metric spaces, including stretch factors, sparsity, and weight/competitive ratios.

Summary of upper and lower bounds for online spanners in various metric spaces.

Discussion and Future Work

While this work significantly advances the state of online spanner construction, several questions remain. It is currently unknown if the $\Omega(\epsilon^{-d})$ lower bound holds for the standard $L_2$ (Euclidean) norm in higher dimensions. Additionally, the use of "Steiner points" (auxiliary junction points) might further improve competitive ratios. Finally, a logarithmic gap ($\log n$) persists between online algorithms and the offline optimum in many scenarios; determining if this gap is inherent to the online model is a primary goal for future research.

Summary updated

Abstract

Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner 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 t-spanner 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(ε^{1-d}log ε^{-1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1-d})⋅ 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 instance-optimal 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 = (2k-1)(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 trade-off 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.
BibTeX
@article{bhore2022online,
  author = {Sujoy Bhore and Arnold Filtser and Hadi Khodabandeh and Csaba D. Tóth},
  title = {{Online Spanners in Metric Spaces}},
  journal = {SIAM J. Discret. Math.},
  year = {2022},
  doi = {10.1137/22m1534572},
}
Figure