Online Spanners in Metric Spaces
Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, Csaba D. Tóth · SIAM Journal on Discrete Mathematics · 2024
Abstract. Given a metric space [Formula: see text], a weighted graph [Formula: see text] over [Formula: see text] is a metric [Formula: see text]-spanner of [Formula: see text] if for every [Formula: see text], [Formula: see text], where [Formula: see text] is the shortest path metric in [Formula: see text]. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points [Formula: see text], where the points are presented one at a time (i.e., after [Formula: see text] steps, we see [Formula: see text]). 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 [Formula: see text]-spanner [Formula: see text] for [Formula: see text] for all [Formula: see text], while minimizing the number of edges, and their total weight. We construct online [Formula: see text]-spanners in the Euclidean [Formula: see text]-space, [Formula: see text]-spanners for general metrics, and [Formula: see text]-spanners for ultrametrics. Most notably, in the Euclidean plane, we construct a [Formula: see text]-spanner with competitive ratio [Formula: see text], bypassing the classic lower bound [Formula: see text] for lightness, which compares the weight of the spanner to that of the minimum spanning tree.