{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T13:13:21Z","timestamp":1776086001546,"version":"3.50.1"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:00:00Z","timestamp":1776038400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:00:00Z","timestamp":1776038400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1910659"],"award-info":[{"award-number":["CCF-1910659"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n In the\n pairwise weighted spanner<\/jats:italic>\n problem, we are given a directed graph with\n n<\/jats:italic>\n vertices and\n k<\/jats:italic>\n terminal vertex pairs. Each edge is assigned both a\n cost<\/jats:italic>\n and a\n length<\/jats:italic>\n . 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\n \n \n $$O(2^{{\\log ^{1-\\varepsilon } n}})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n \n \n log<\/mml:mo>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\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\n integral<\/jats:italic>\n lengths with magnitudes\n polynomial<\/jats:italic>\n in\n n<\/jats:italic>\n , we show an\n \n \n $$\\tilde{O}(n^{4\/5 + \\varepsilon })$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 4<\/mml:mn>\n \/<\/mml:mo>\n 5<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation algorithm. When the edges have unit costs and lengths, the best previous algorithm gives an\n \n \n $$\\tilde{O}(n^{3\/5 + \\varepsilon })$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 5<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation, due to Chlamt\u00e1\u010d, Dinitz, Kortsarz, and Laekhanukit (Transactions on Algorithms, 2020). We also consider the\n online<\/jats:italic>\n setting, where the vertex pairs arrive one at a time, and edges must be added irrevocably to satisfy the distance constraints. We show an\n \n \n $$\\tilde{O}(k^{1\/2 + \\varepsilon })$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n k<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -competitive algorithm. The state-of-the-art results are an\n \n \n $$\\tilde{O}(n^{4\/5})$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 4<\/mml:mn>\n \/<\/mml:mo>\n 5<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -competitive algorithm when edges have unit costs and arbitrary positive lengths, and a\n \n \n $$\\min \\{\\tilde{O}(k^{1\/2 + \\varepsilon }), \\tilde{O}(n^{2\/3 + \\varepsilon })\\}$$<\/jats:tex-math>\n \n \n min<\/mml:mo>\n {<\/mml:mo>\n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n k<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 2<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -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.\n <\/jats:p>","DOI":"10.1007\/s00453-026-01384-6","type":"journal-article","created":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T12:39:54Z","timestamp":1776083994000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for Directed Weighted Spanners"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9673-4313","authenticated-orcid":false,"given":"Elena","family":"Grigorescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nithish","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5719-6708","authenticated-orcid":false,"given":"Young-San","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,13]]},"reference":[{"key":"1384_CR1","doi-asserted-by":"publisher","unstructured":"Awerbuch, B.: Communication-time trade-offs in network synchronization. In: Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, pp. 272\u2013276. Association for Computing Machinery, New York, NY, USA (1985). https:\/\/doi.org\/10.1145\/323596.323621","DOI":"10.1145\/323596.323621"},{"issue":"1","key":"1384_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99\u2013116 (1989). https:\/\/doi.org\/10.1002\/jgt.3190130114","journal-title":"J. Graph Theory"},{"key":"1384_CR3","doi-asserted-by":"publisher","unstructured":"Yao, A.C.: Space-time tradeoff for answering range queries. In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 128\u2013136 (1982). https:\/\/doi.org\/10.1145\/800070.802185","DOI":"10.1145\/800070.802185"},{"key":"1384_CR4","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical report (1987)"},{"issue":"4","key":"1384_CR5","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1145\/41840.41847","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18(4), 740\u2013747 (1989). https:\/\/doi.org\/10.1145\/41840.41847","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1384_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1145\/343477.343516","volume":"50","author":"LJ Cowen","year":"2004","unstructured":"Cowen, L.J., Wagner, C.G.: Compact roundtrip routing in directed networks. J. Algorithms 50(1), 79\u201395 (2004). https:\/\/doi.org\/10.1145\/343477.343516","journal-title":"J. Algorithms"},{"issue":"3","key":"1384_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1367064.1367069","volume":"4","author":"L Roditty","year":"2008","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms (TALG) 4(3), 1\u201317 (2008). https:\/\/doi.org\/10.1145\/1367064.1367069","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"1384_CR8","doi-asserted-by":"publisher","unstructured":"Pachocki, J., Roditty, L., Sidford, A., Tov, R., Williams, V.V.: Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners. In: Proceedings of the Twenty-ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1374\u20131392 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.91 . SIAM","DOI":"10.1137\/1.9781611975031.91"},{"issue":"5","key":"1384_CR9","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1109\/sfcs.1996.548504","volume":"29","author":"D Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29(5), 1740\u20131759 (2000). https:\/\/doi.org\/10.1109\/sfcs.1996.548504","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1384_CR10","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/383962.383983","volume":"1","author":"M Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Trans. Algorithms (TALG) 1(2), 283\u2013323 (2005). https:\/\/doi.org\/10.1145\/383962.383983","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"7","key":"1384_CR11","doi-asserted-by":"publisher","first-page":"2865","DOI":"10.1137\/080737174","volume":"39","author":"S Baswana","year":"2010","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM J. Comput. 39(7), 2865\u20132896 (2010). https:\/\/doi.org\/10.1137\/080737174","journal-title":"SIAM J. Comput."},{"key":"1384_CR12","doi-asserted-by":"publisher","unstructured":"Chechik, S.: Approximate distance oracles with improved bounds. In: Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, pp. 1\u201310 (2015). https:\/\/doi.org\/10.1145\/2746539.2746562","DOI":"10.1145\/2746539.2746562"},{"issue":"1","key":"1384_CR13","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1109\/focs.2010.83","volume":"43","author":"M Patrascu","year":"2014","unstructured":"Patrascu, M., Roditty, L.: Distance oracles beyond the Thorup-Zwick bound. SIAM J. Comput. 43(1), 300\u2013311 (2014). https:\/\/doi.org\/10.1109\/focs.2010.83","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1384_CR14","doi-asserted-by":"publisher","first-page":"1380","DOI":"10.1137\/1.9781611973068.101","volume":"41","author":"A Bhattacharyya","year":"2012","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.P.: Transitive-closure spanners. SIAM J. Comput. 41(6), 1380\u20131425 (2012). https:\/\/doi.org\/10.1137\/1.9781611973068.101","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1384_CR15","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1007\/s00453-015-9984-y","volume":"74","author":"P Awasthi","year":"2016","unstructured":"Awasthi, P., Jha, M., Molinaro, M., Raskhodnikova, S.: Testing lipschitz functions on hypergrid domains. Algorithmica 74(3), 1055\u20131081 (2016). https:\/\/doi.org\/10.1007\/s00453-015-9984-y","journal-title":"Algorithmica"},{"key":"1384_CR16","doi-asserted-by":"publisher","unstructured":"Gupta, A., Kumar, A., P\u00e1l, M., Roughgarden, T.: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: Proceedings of the Forty-fourth Annual IEEE Symposium on Foundations of Computer Science, pp. 606\u2013615 (2003). https:\/\/doi.org\/10.1109\/sfcs.2003.1238233 . IEEE","DOI":"10.1109\/sfcs.2003.1238233"},{"key":"1384_CR17","doi-asserted-by":"publisher","unstructured":"Kumar, A., Gupta, A., Roughgarden, T.: A constant-factor approximation algorithm for the multicommodity rent-or-buy problem. In: Proceedings of the Forty-third Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 333\u2013342 (2002). https:\/\/doi.org\/10.1109\/sfcs.2002.1181956 . IEEE","DOI":"10.1109\/sfcs.2002.1181956"},{"key":"1384_CR18","doi-asserted-by":"publisher","unstructured":"Fleischer, L., K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G.: Simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree. In: Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, pp. 663\u2013670 (2006). https:\/\/doi.org\/10.1145\/1132516.1132609","DOI":"10.1145\/1132516.1132609"},{"issue":"5","key":"1384_CR19","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1137\/050646408","volume":"37","author":"J K\u00f6nemann","year":"2008","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G., Zwam, S.H.: A group-strategyproof cost sharing mechanism for the steiner forest game. SIAM J. Comput. 37(5), 1319\u20131341 (2008). https:\/\/doi.org\/10.1137\/050646408","journal-title":"SIAM J. Comput."},{"key":"1384_CR20","doi-asserted-by":"publisher","unstructured":"Chawla, S., Roughgarden, T., Sundararajan, M.: Optimal cost-sharing mechanisms for steiner forest problems. In: International Workshop on Internet and Network Economics, pp. 112\u2013123 (2006). https:\/\/doi.org\/10.1007\/11944874_11 . Springer","DOI":"10.1007\/11944874_11"},{"key":"1384_CR21","doi-asserted-by":"publisher","unstructured":"Roughgarden, T., Sundararajan, M.: Optimal efficiency guarantees for network design mechanisms. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 469\u2013483 (2007). https:\/\/doi.org\/10.1007\/978-3-540-72792-7_35 . Springer","DOI":"10.1007\/978-3-540-72792-7_35"},{"key":"1384_CR22","doi-asserted-by":"publisher","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G., Zwam, S.: From primal-dual to cost shares and back: a stronger lp relaxation for the steiner forest problem. In: International Colloquium on Automata, Languages, and Programming, pp. 930\u2013942 (2005). https:\/\/doi.org\/10.1007\/11523468_75 . Springer","DOI":"10.1007\/11523468_75"},{"issue":"9","key":"1384_CR23","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1038\/nmeth.3940","volume":"13","author":"L Pirhaji","year":"2016","unstructured":"Pirhaji, L., Milani, P., Leidl, M., Curran, T., Avila-Pacheco, J., Clish, C.B., White, F.M., Saghatelian, A., Fraenkel, E.: Revealing disease-associated pathways by network integration of untargeted metabolomics. Nat. Methods 13(9), 770\u2013776 (2016). https:\/\/doi.org\/10.1038\/nmeth.3940","journal-title":"Nat. Methods"},{"issue":"2","key":"1384_CR24","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.cels.2016.12.011","volume":"4","author":"V Khurana","year":"2017","unstructured":"Khurana, V., Peng, J., Chung, C.Y., Auluck, P.K., Fanning, S., Tardiff, D.F., Bartels, T., Koeva, M., Eichhorn, S.W., Benyamini, H.: Genome-scale networks link neurodegenerative disease genes to $$\\alpha $$-synuclein through specific molecular pathways. Cell Syst. 4(2), 157\u2013170 (2017). https:\/\/doi.org\/10.1016\/j.cels.2016.12.011","journal-title":"Cell Syst."},{"issue":"3","key":"1384_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/focs.2008.59","volume":"11","author":"G Borradaile","year":"2015","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for euclidean steiner forest. ACM Trans. Algorithms (TALG) 11(3), 1\u201320 (2015). https:\/\/doi.org\/10.1109\/focs.2008.59","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3\u20134","key":"1384_CR26","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1007\/s00453-011-9491-8","volume":"62","author":"M Bateni","year":"2012","unstructured":"Bateni, M., Hajiaghayi, M.: Euclidean prize-collecting steiner forest. Algorithmica 62(3\u20134), 906\u2013929 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9491-8","journal-title":"Algorithmica"},{"key":"1384_CR27","doi-asserted-by":"publisher","unstructured":"Kortsarz, G.: On the hardness of approximating spanners. Algorithmica 30, 432\u2013450 (2001) https:\/\/doi.org\/10.1007\/s00453-001-0021-y","DOI":"10.1007\/s00453-001-0021-y"},{"issue":"4","key":"1384_CR28","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s00224-006-1266-2","volume":"41","author":"M Elkin","year":"2007","unstructured":"Elkin, M., Peleg, D.: The hardness of approximating spanner problems. Theory Comput. Syst. 41(4), 691\u2013729 (2007). https:\/\/doi.org\/10.1007\/s00224-006-1266-2","journal-title":"Theory Comput. Syst."},{"key":"1384_CR29","unstructured":"Elkin, M., Peleg, D.: The client-server 2-spanner problem with applications to network design. In: SIROCCO 8, Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity, Vall de N\u00faria, Girona-Barcelona, Catalonia, Spain, 27-29 June, 2001, pp. 117\u2013132 (2001). Carleton Scientific"},{"key":"1384_CR30","doi-asserted-by":"publisher","unstructured":"Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S., Yaroslavtsev, G.: Approximation algorithms for spanner problems and directed steiner forest. Information and Computation 222, 93\u2013107 (2013) https:\/\/doi.org\/10.1016\/j.ic.2012.10.007","DOI":"10.1016\/j.ic.2012.10.007"},{"key":"1384_CR31","doi-asserted-by":"publisher","unstructured":"Dinitz, M., Zhang, Z.: Approximating low-stretch spanners. In: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 821\u2013840 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch59 . SIAM","DOI":"10.1137\/1.9781611974331.ch59"},{"key":"1384_CR32","doi-asserted-by":"publisher","unstructured":"Grigorescu, E., Lin, Y.-S., Quanrud, K.: Online directed spanners and steiner forests. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2021). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2021.5","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.5"},{"issue":"3","key":"1384_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/1.9781611974782.34","volume":"16","author":"E Chlamt\u00e1\u010d","year":"2020","unstructured":"Chlamt\u00e1\u010d, E., Dinitz, M., Kortsarz, G., Laekhanukit, B.: Approximating spanners and directed steiner forest: Upper and lower bounds. ACM Trans. Algorithms (TALG) 16(3), 1\u201331 (2020). https:\/\/doi.org\/10.1137\/1.9781611974782.34","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"2","key":"1384_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1921659.1921664","volume":"7","author":"C Chekuri","year":"2011","unstructured":"Chekuri, C., Even, G., Gupta, A., Segev, D.: Set connectivity problems in undirected graphs and the directed steiner network problem. ACM Trans. Algorithms (TALG) 7(2), 1\u201317 (2011). https:\/\/doi.org\/10.1145\/1921659.1921664","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"1384_CR35","doi-asserted-by":"publisher","unstructured":"Abboud, A., Bodwin, G.: Reachability preservers: New extremal bounds and approximation algorithms. In: Proceedings of the Twenty-ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1865\u20131883 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.122 . SIAM","DOI":"10.1137\/1.9781611975031.122"},{"issue":"1","key":"1384_CR36","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin, R.: Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17(1), 36\u201342 (1992). https:\/\/doi.org\/10.1287\/moor.17.1.36","journal-title":"Math. Oper. Res."},{"issue":"5","key":"1384_CR37","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/s0167-6377(01)00069-4","volume":"28","author":"DH Lorenz","year":"2001","unstructured":"Lorenz, D.H., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28(5), 213\u2013219 (2001). https:\/\/doi.org\/10.1016\/s0167-6377(01)00069-4","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1384_CR38","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1137\/19m123662x","volume":"50","author":"G Bodwin","year":"2021","unstructured":"Bodwin, G.: New results on linear size distance preservers. SIAM J. Comput. 50(2), 662\u2013673 (2021). https:\/\/doi.org\/10.1137\/19m123662x","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1384_CR39","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/s0097539793256685","volume":"24","author":"S Khuller","year":"1995","unstructured":"Khuller, S., Raghavachari, B., Young, N.: Approximating the minimum equivalent digraph. SIAM J. Comput. 24(4), 859\u2013872 (1995). https:\/\/doi.org\/10.1137\/s0097539793256685","journal-title":"SIAM J. Comput."},{"key":"1384_CR40","doi-asserted-by":"publisher","unstructured":"Vetta, A.: Approximating the minimum strongly connected subgraph via a matching lower bound. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 417\u2013426 (2001). https:\/\/doi.org\/10.5555\/365411.365493","DOI":"10.5555\/365411.365493"},{"issue":"1","key":"1384_CR41","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T.-Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed steiner problems. J. Algorithms 33(1), 73\u201391 (1999). https:\/\/doi.org\/10.1006\/jagm.1999.1042","journal-title":"J. Algorithms"},{"issue":"4","key":"1384_CR42","doi-asserted-by":"publisher","first-page":"1505","DOI":"10.1109\/focs.2015.40","volume":"47","author":"D Chakrabarty","year":"2018","unstructured":"Chakrabarty, D., Ene, A., Krishnaswamy, R., Panigrahi, D.: Online buy-at-bulk network design. SIAM J. Comput. 47(4), 1505\u20131528 (2018). https:\/\/doi.org\/10.1109\/focs.2015.40","journal-title":"SIAM J. Comput."},{"key":"1384_CR43","doi-asserted-by":"publisher","unstructured":"Dinitz, M., Krauthgamer, R.: Directed spanners via flow-based linear programs. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, pp. 323\u2013332 (2011). https:\/\/doi.org\/10.1145\/1993636.1993680","DOI":"10.1145\/1993636.1993680"},{"issue":"1","key":"1384_CR44","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/j.jcss.2011.05.009","volume":"78","author":"M Feldman","year":"2012","unstructured":"Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximation algorithms for directed steiner forest. J. Comput. Syst. Sci. 78(1), 279\u2013292 (2012). https:\/\/doi.org\/10.1016\/j.jcss.2011.05.009","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1384_CR45","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s11590-017-1212-z","volume":"12","author":"M Horv\u00e1th","year":"2018","unstructured":"Horv\u00e1th, M., Kis, T.: Multi-criteria approximation schemes for the resource constrained shortest path problem. Optim. Lett. 12(3), 475\u2013483 (2018). https:\/\/doi.org\/10.1007\/s11590-017-1212-z","journal-title":"Optim. Lett."},{"issue":"1","key":"1384_CR46","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"MV Marathe","year":"1998","unstructured":"Marathe, M.V., Sundaram, R., Ravi, S., Rosenkrantz, D.J., Hunt, H.B., III.: Bicriteria network design problems. J. Algorithms 28(1), 142\u2013171 (1998). https:\/\/doi.org\/10.1006\/jagm.1998.0930","journal-title":"J. Algorithms"},{"key":"1384_CR47","doi-asserted-by":"publisher","unstructured":"Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R.: Approximating buy-at-bulk and shallow-light $$k$$-steiner trees. Algorithmica 53, 89\u2013103 (2009) https:\/\/doi.org\/10.1007\/s00453-007-9013-x","DOI":"10.1007\/s00453-007-9013-x"},{"key":"1384_CR48","doi-asserted-by":"publisher","unstructured":"Haeupler, B., Hershkowitz, D.E., Zuzic, G.: Tree embeddings for hop-constrained network design. In: Proceedings of the Fifty-third Annual ACM Symposium on Theory of Computing, pp. 356\u2013369 (2021). https:\/\/doi.org\/10.1145\/3406325.3451053","DOI":"10.1145\/3406325.3451053"},{"key":"1384_CR49","doi-asserted-by":"publisher","unstructured":"Filtser, A.: Hop-constrained metric embeddings and their applications. In: Proceedings of the Sixty-second Annual IEEE Symposium on Foundations of Computer Science, pp. 492\u2013503 (2021). https:\/\/doi.org\/10.1109\/focs52979.2021.00056 . IEEE","DOI":"10.1109\/focs52979.2021.00056"},{"issue":"1","key":"1384_CR50","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/bf02523690","volume":"18","author":"A Zelikovsky","year":"1997","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica 18(1), 99\u2013110 (1997). https:\/\/doi.org\/10.1007\/bf02523690","journal-title":"Algorithmica"},{"key":"1384_CR51","doi-asserted-by":"publisher","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, pp. 169\u2013178 (2011). https:\/\/doi.org\/10.1145\/1993806.1993830","DOI":"10.1145\/1993806.1993830"},{"issue":"8","key":"1384_CR52","doi-asserted-by":"publisher","first-page":"2292","DOI":"10.1007\/s00453-021-00911-x","volume":"84","author":"FV Fomin","year":"2022","unstructured":"Fomin, F.V., Golovach, P.A., Lochet, W., Misra, P., Saurabh, S., Sharma, R.: Parameterized complexity of directed spanner problems. Algorithmica 84(8), 2292\u20132308 (2022). https:\/\/doi.org\/10.1007\/s00453-021-00911-x","journal-title":"Algorithmica"},{"key":"1384_CR53","doi-asserted-by":"publisher","unstructured":"Ahmed, R., Bodwin, G., Sahneh, F.D., Hamm, K., Jebelli, M.J.L., Kobourov, S., Spence, R.: Graph spanners: A tutorial review. Computer Science Review 37, 100253 (2020) https:\/\/doi.org\/10.1016\/j.cosrev.2020.100253","DOI":"10.1016\/j.cosrev.2020.100253"},{"key":"1384_CR54","doi-asserted-by":"publisher","unstructured":"Kogan, S., Parter, M.: Having hope in hops: New spanners, preservers and lower bounds for hopsets. In: Proceddings of the Sixty-third Annual IEEE Symposium on Foundations of Computer Science, pp. 766\u2013777 (2022). https:\/\/doi.org\/10.1109\/focs54457.2022.00078 . IEEE","DOI":"10.1109\/focs54457.2022.00078"},{"key":"1384_CR55","doi-asserted-by":"publisher","unstructured":"Antonakopoulos, S.: Approximating directed buy-at-bulk network design. In: International Workshop on Approximation and Online Algorithms, pp. 13\u201324 (2010). https:\/\/doi.org\/10.1007\/978-3-642-18318-8_2 . Springer","DOI":"10.1007\/978-3-642-18318-8_2"},{"issue":"4","key":"1384_CR56","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/1198513.1198522","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: A general approach to online network optimization problems. ACM Trans. Algorithms 2(4), 640\u2013660 (2006). https:\/\/doi.org\/10.1145\/1198513.1198522","journal-title":"ACM Trans. Algorithms"},{"key":"1384_CR57","doi-asserted-by":"crossref","unstructured":"Helvig, C.S., Robins, G., Zelikovsky, A.: An improved approximation scheme for the group steiner problem. Networks: An International Journal 37(1), 8\u201320 (2001)","DOI":"10.1002\/1097-0037(200101)37:1<8::AID-NET2>3.0.CO;2-R"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01384-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01384-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01384-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T12:40:01Z","timestamp":1776084001000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01384-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,13]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["1384"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01384-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,13]]},"assertion":[{"value":"20 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"38"}}