.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithms for Directed Weighted Spanners
.png){kind=icon}
PRE
AI
DOI：10.1007/s00453-026-01384-6.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In the pairwise weighted spanner problem, we are given a directed graph with n vertices and k terminal vertex pairs. Each edge is assigned both a cost and a length. The goal is to find a minimum-cost subgraph in which the terminal distance constraints are satisfied. A more restricted variant of this problem was shown to be O(2(log1-epsilon n))-hard to approximate under a standard complexity assumption, by Elkin and Peleg (Theory of Computing Systems, 2007). This general formulation captures many well-studied network connectivity problems, including spanners, distance preservers, and Steiner forests. For the weighted spanner problem where the edges have positive integral lengths with magnitudes polynomial in n, we show an O(n(4/5+epsilon))-approximation algorithm. When the edges have unit costs and lengths, the best previous algorithm gives an O(n(3/5+epsilon))-approximation, due to Chlamt & aacute;& ccaron;, Dinitz, Kortsarz, and Laekhanukit (Transactions on Algorithms, 2020). We also consider the online setting, where the vertex pairs arrive one at a time, and edges must be added irrevocably to satisfy the distance constraints. We show an O(n(1/2+epsilon))-competitive algorithm. The state-of-the-art results are an O(n(4/5))-competitive algorithm when edges have unit costs and arbitrary positive lengths, and a min{O(n(1/2+epsilon)),O(n(2/3+epsilon)) -competitive algorithm when edges have unit costs and lengths, due to Grigorescu, Lin, and Quanrud (APPROX, 2021). To the best of our knowledge, our results are the first approximation (online) polynomial-time algorithms with sublinear approximation (competitive) ratios for the weighted spanner problems.
Keywords:
Directed spanners
Directed steiner forests
Approximation algorithms
Online algorithms