Abstract
In the pairwise weighted spanner problem, the input consists of a weighted directed graph on n vertices, where each edge is assigned both a cost and a length. Furthermore, we are given k terminal vertex pairs and a distance constraint for each pair. The goal is to find a minimumcost subgraph in which the distance constraints are satisfied.
We study the weighted spanner problem, in which the edges have positive integral lengths of magnitudes that are polynomial in n, while the costs are arbitrary nonnegative rational numbers. Our results include the following in the classical offline setting:
 An Õ(n^{4/5 + ε})approximation algorithm for the weighted pairwise spanner problem. When the edges have unit costs and lengths, the best previous algorithm gives an Õ(n^{3/5 + ε})approximation, due to Chlamtáč, Dinitz, Kortsarz, and Laekhanukit (Transactions on Algorithms, 2020).
 An Õ(n^{1/2+ε})approximation algorithm for the weighted spanner problem when the terminal pairs consist of all vertex pairs and the distances must be preserved exactly. When the edges have unit costs and arbitrary positive lengths, the best previous algorithm gives an Õ(n^{1/2})approximation for the allpair spanner problem, due to Berman, Bhattacharyya, Makarychev, Raskhodnikova, and Yaroslavtsev (Information and Computation, 2013). We also prove the first results for the weighted spanners in the online setting. Our results include the following:
 An Õ(k^{1/2 + ε})competitive algorithm for the online weighted pairwise spanner problem. The stateoftheart results are an Õ(n^{4/5})competitive algorithm when edges have unit costs and arbitrary positive lengths, and a min{Õ(k^{1/2 + ε}), Õ(n^{2/3 + ε})}competitive algorithm when edges have unit costs and lengths, due to Grigorescu, Lin, and Quanrud (APPROX, 2021).
 An Õ(k^ε)competitive algorithm for the online weighted singlesource (or singlesink) spanner problem. Without distance constraints, this problem is equivalent to the online directed Steiner tree problem. The best previous algorithm for online directed Steiner trees is an Õ(k^ε)competitive algorithm, due to Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP, 2018). Our online results also imply efficient approximation algorithms for the corresponding offline problems. To the best of our knowledge, these are the first approximation (online) polynomialtime algorithms with sublinear approximation (competitive) ratios for the weighted spanner problems.
BibTeX  Entry
@InProceedings{grigorescu_et_al:LIPIcs.APPROX/RANDOM.2023.8,
author = {Grigorescu, Elena and Kumar, Nithish and Lin, YoungSan},
title = {{Approximation Algorithms for Directed Weighted Spanners}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {8:18:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18833},
URN = {urn:nbn:de:0030drops188335},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.8},
annote = {Keywords: directed weighted spanners, linear programming, junction tree}
}
Keywords: 

directed weighted spanners, linear programming, junction tree 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 