EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Approximation Algorithms for Directed Weighted Spanners

Elena Grigorescu, Nithish Kumar, Young-San Lin

Algorithmica · 2026-06 · 88 (3)

DOI: 10.1007/s00453-026-01384-6 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 13.04.2026. Verfasst von Elena Grigorescu und 2 weiteren Autor:innen. Die Arbeit nennt 57 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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^{{\log ^{1-\varepsilon } n}})$$ O ( 2 log 1 - ε 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 $$\tilde{O}(n^{4/5 + \varepsilon })$$ O ~ ( n 4 / 5 + ε ) -approximation algorithm. When the edges have unit costs and lengths, the best previous algorithm gives an $$\tilde{O}(n^{3/5 + \varepsilon })$$ O ~ ( n 3 / 5 + ε ) -approximation, due to Chlamtáč, 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 $$\tilde{O}(k^{1/2 + \varepsilon })$$ O ~ ( k 1 / 2 + ε ) -competitive algorithm. The state-of-the-art results are an $$\tilde{O}(n^{4/5})$$ O ~ ( n 4 / 5 ) -competitive algorithm when edges have unit costs and arbitrary positive lengths, and a $$\min \{\tilde{O}(k^{1/2 + \varepsilon }), \tilde{O}(n^{2/3 + \varepsilon })\}$$ min { O ~ ( k 1 / 2 + ε ) , O ~ ( n 2 / 3 + ε ) } -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.

Förderung

  • National Science Foundation

Zitieren

APA

Grigorescu, E., Kumar, N., & Lin, Y. (2026). Approximation Algorithms for Directed Weighted Spanners. Algorithmica, 88(3). https://doi.org/10.1007/s00453-026-01384-6

Vancouver

Grigorescu E, Kumar N, Lin Y. Approximation Algorithms for Directed Weighted Spanners. Algorithmica. 2026;88(3). doi:10.1007/s00453-026-01384-6

BibTeX
@article{Grigorescu2026,
  author = {Grigorescu, Elena and Kumar, Nithish and Lin, Young-San},
  title = {Approximation Algorithms for Directed Weighted Spanners},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {3},
  doi = {10.1007/s00453-026-01384-6}
}
Kostenlos starten →