Abstract 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 ~ (

We present a framework that unifies directed buy-at-bulk network design and directed spanner problems, namely, buy-at-bulk spanners. The goal is to find a minimum-cost routing solution for network design problems that captures economies at scale, while satisfying demands and distance constraints for terminal pairs. A more restricted version of this problem was shown to be O(2^{log^{1-ε} n})-hard to approximate, where n is the number of vertices, under a standard complexity assumption, by Elkin and Peleg (Theory of Computing Systems, 2007). Our results for buy-at-bulk spanners are the following. - When the edge lengths are integral with magnitude polynomial in n we present: 1) An Õ(n^{4/5 + ε})-approximation polynomial-time randomized algorithm for uniform demands. 2) An Õ(k^{1/2 + ε})-approximation polynomial-time randomized algorithm for general demands, where k is the number of terminal pairs. This can be improved to an Õ(k^{ε})-approximation algorithm for the single-source problem. The same approximation ratios hold in the online setting. - When the edge lengths are rational and well-conditioned, we present an Õ(k^{1/2 + ε})-approximation polynomial-time randomized algorithm that may slightly violate the distance constraints. The result can be improved to an Õ(k^ε)-approximation algorithm for the single-source problem. The same approximation ratios hold for the online setting when the condition number is given in advance. To the best of our knowledge, these are the first sublinear factor approximation algorithms for directed buy-at-bulk spanners. We allow the edge lengths to be negative and the demands to be non-unit, unlike the previous literature. Our approximation ratios match the state-of-the-art ratios in special cases, namely, buy-at-bulk network design by Antonakopoulos (WAOA, 2010) and (online) weighted spanners by Grigorescu, Kumar, and Lin (APPROX 2023). Furthermore, we improve the competitive ratio for online buy-at-bulk by Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP, 2018) by a factor of log R, where R is the ratio between the maximum demand and the minimum demand.