Online spanners in metric spaces

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