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}})\) -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 })\) -approximation algorithm. When the edges have unit costs and lengths, the best previous algorithm gives an \(\tilde{O}(n^{3/5 + \varepsilon })\) -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 })\) -competitive algorithm. The state-of-the-art results are an \(\tilde{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 })\}\) -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.
