Online Directed Spanners and Steiner Forests

by Elena Grigorescu, Young-San Lin, and Kent Quanrud

Theory of Computing, Volume 22(2077), pp. 1-53, 2026

Bibliography with links to cited articles

[1]   Amir Abboud and Greg Bodwin: Reachability preservers: New extremal bounds and approximation algorithms. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1865–1883. SIAM, 2018. [doi:10.1137/1.9781611975031.122]

[2]   Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence: Graph spanners: A tutorial review, 2020. [doi:10.1016/j.cosrev.2020.100253]

[3]   Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor: A general approach to online network optimization problems. ACM Transactions on Algorithms (TALG), 2(4):640–660, 2006. [doi:10.1145/1198513.1198522]

[4]   Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor: The online set cover problem. SIAM Journal on Computing, 39(2):361–370, 2009. [doi:10.1137/060661946]

[5]   Noga Alon and Baruch Schieber: Optimal preprocessing for answering on-line product queries. Citeseer, 1987.

[6]   Spyridon Antonakopoulos: Approximating directed buy-at-bulk network design. In Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA), pp. 13–24. Springer, 2010. [doi:10.1007/978-3-642-18318-8_2]

[7]   Esther M Arkin, Joseph SB Mitchell, and Christine D Piatko: Bicriteria shortest path problems in the plane. In Proceedings of the 3rd Canadian Conference on Computational Geometry, pp. 153–156, 1991.

[8]   Pranjal Awasthi, Madhav Jha, Marco Molinaro, and Sofya Raskhodnikova: Testing lipschitz functions on hypergrid domains. Algorithmica, 74(3):1055–1081, 2016. [doi:10.1007/s00453-015-9984-y]

[9]   Baruch Awerbuch: Communication-time trade-offs in network synchronization. In Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing (PODC), p. 272–276, New York, NY, USA, 1985. ACM. [doi:10.1145/323596.323621]

[10]   Baruch Awerbuch and Yossi Azar: Buy-at-bulk network design. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 542–547. IEEE, 1997. [doi:10.1109/SFCS.1997.646143]

[11]   Baruch Awerbuch, Yossi Azar, and Yair Bartal: On-line generalized steiner problem. Theoretical Computer Science, 324(2-3):313–324, 2004. [doi:10.1016/j.tcs.2004.05.021]

[12]   Baruch Awerbuch, Yossi Azar, and Serge Plotkin: Throughput-competitive on-line routing. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS), pp. 32–40. IEEE, 1993. [doi:10.1109/SFCS.1993.366884]

[13]   Yossi Azar, Umang Bhaskar, Lisa Fleischer, and Debmalya Panigrahi: Online mixed packing and covering. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 85–100. SIAM, 2013. [doi:10.1137/1.9781611973105.6]

[14]   Yossi Azar, Niv Buchbinder, TH Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, et al.: Online algorithms for covering and packing problems with convex objectives. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 148–157. IEEE, 2016. [doi:10.1109/FOCS.2016.24]

[15]   Nikhil Bansal, Niv Buchbinder, and Joseph Naor: Randomized competitive algorithms for generalized caching. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 235–244, 2008. [doi:10.1145/1374376.1374412]

[16]   Nikhil Bansal, Niv Buchbinder, and Joseph Naor: A primal-dual randomized algorithm for weighted paging. Journal of the ACM (JACM), 59(4):1–24, 2012. [doi:10.1145/2339123.2339126]

[17]   Surender Baswana: Streaming algorithm for graph spanners - single pass and constant processing time per edge. Information Processing Letters, 106(3):110–114, 2008. [doi:10.1016/j.ipl.2007.11.001]

[18]   Surender Baswana and Telikepalli Kavitha: Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM Journal on Computing, 39(7):2865–2896, 2010. [doi:10.1137/080737174]

[19]   MohammadHossein Bateni and MohammadTaghi Hajiaghayi: Euclidean prize-collecting steiner forest. Algorithmica, 62(3-4):906–929, 2012. [doi:10.1007/s00453-011-9491-8]

[20]   Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev: Approximation algorithms for spanner problems and directed steiner forest. Information and Computation, 222:93–107, 2013. [doi:10.1016/j.ic.2012.10.007]

[21]   Piotr Berman and Chris Coulston: On-line algorithms for steiner tree problems (extended abstract). In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 344–353, 1997. [doi:10.1145/258533.258618]

[22]   Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P Woodruff: Transitive-closure spanners. SIAM Journal on Computing, 41(6):1380–1425, 2012. [doi:10.1137/110826655]

[23]   Greg Bodwin and Virginia Vassilevska Williams: Better distance preservers and additive spanners. ACM Transactions on Algorithms (TALG), 17(4):1–24, 2021. [doi:10.1145/3490147]

[24]   Glencora Borradaile, Philip N Klein, and Claire Mathieu: A polynomial-time approximation scheme for euclidean steiner forest. ACM Transactions on Algorithms (TALG), 11(3):1–20, 2015. [doi:10.1145/2629654]

[25]   Niv Buchbinder and Joseph Naor: Improved bounds for online routing and packing via a primal-dual approach. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 293–304. IEEE, 2006. [doi:10.1109/FOCS.2006.39]

[26]   Niv Buchbinder and Joseph Naor: Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):270–286, 2009. [doi:10.1287/moor.1080.0363]

[27]   Niv Buchbinder and Joseph Seffi Naor: The design of competitive online algorithms via a primal–dual approach. Foundations and Trends® in Theoretical Computer Science, 3(2–3):93–263, 2009. [doi:10.1561/0400000024]

[28]   Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, and Debmalya Panigrahi: Online buy-at-bulk network design. SIAM Journal on Computing, 47(4):1505–1528, 2018. [doi:10.1137/16M1117317]

[29]   Moses Charikar, Chandra Chekuri, To-yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li: Approximation algorithms for directed steiner problems. Journal of Algorithms, 33(1):73–91, 1999. [doi:10.1006/jagm.1999.1042]

[30]    Shuchi Chawla, Tim Roughgarden, and Mukund Sundararajan: Optimal cost-sharing mechanisms for steiner forest problems. In Proceedings of the 2nd International Workshop on Internet and Network Economics (WINE), pp. 112–123. Springer, 2006. [doi:10.1007/11944874_11]

[31]   Shiri Chechik: Approximate distance oracles with improved bounds. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pp. 1–10, 2015. [doi:10.1145/2746539.2746562]

[32]   Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev: Set connectivity problems in undirected graphs and the directed steiner network problem. ACM Transactions on Algorithms (TALG), 7(2):1–17, 2011. [doi:10.1145/1921659.1921664]

[33]   Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, and Mohammad R Salavatipour: Approximation algorithms for nonuniform buy-at-bulk network design. SIAM Journal on Computing, 39(5):1772–1798, 2010. [doi:10.1137/090750317]

[34]   Eden Chlamtáč, Michael Dinitz, Guy Kortsarz, and Bundit Laekhanukit: Approximating spanners and directed steiner forest: Upper and lower bounds. ACM Transactions on Algorithms (TALG), 16(3):1–31, 2020. [doi:10.1145/3381451]

[35]   Lenore Cowen and Christopher G. Wagner: Compact roundtrip routing in directed networks. Journal of Algorithms, 50(1):79–95, 2004. [doi:10.1016/j.jalgor.2003.08.001]

[36]   Bilel Derbel, Cyril Gavoille, and David Peleg: Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In Andrzej Pelc, editor, DISC, volume 4731 of Lecture Notes in Computer Science, pp. 179–192. Springer, 2007. [doi:10.1007/978-3-540-75142-7_16]

[37]   Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot: On the locality of distributed sparse spanner construction. In Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 273–282, 2008. [doi:10.1145/1400751.1400788]

[38]   Michael Dinitz and Robert Krauthgamer: Directed spanners via flow-based linear programs. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 323–332, 2011. [doi:10.1145/1993636.1993680]

[39]   Michael Dinitz, Yasamin Nazari, and Zeyu Zhang: Lasserre integrality gaps for graph spanners and related problems. In Proceedings of the 19th International Workshop on Approximation and Online Algorithms (WAOA), pp. 97–112. Springer, 2021. [doi:10.1007/978-3-030-80879-2_7]

[40]   Michael Dinitz and Zeyu Zhang: Approximating low-stretch spanners. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 821–840. SIAM, 2016. [doi:10.1137/1.9781611974331.ch59]

[41]   Dorit Dor, Shay Halperin, and Uri Zwick: All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740–1759, 2000. [doi:10.1137/S0097539797327908]

[42]   Michael Elkin: Computing almost shortest paths. ACM Transactions on Algorithms (TALG), 1(2):283–323, 2005. [doi:10.1145/1103963.1103968]

[43]   Michael Elkin: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms (TALG), 7(2):1–17, 2011. [doi:10.1145/1921659.1921666]

[44]   Michael Elkin and David Peleg: The client-server 2-spanner problem with applications to network design. In Francesc Comellas, Josep Fàbrega, and Pierre Fraigniaud, editors, SIROCCO 8, Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity, Vall de Núria, Girona-Barcelona, Catalonia, Spain, 27-29 June, 2001, volume 8 of Proceedings in Informatics, pp. 117–132. Carleton Scientific, 2001.

[45]   Michael Elkin and David Peleg: The hardness of approximating spanner problems. Theory of Computing Systems, 41(4):691–729, 2007. [doi:10.1007/s00224-006-1266-2]

[46]   Moran Feldman, Guy Kortsarz, and Zeev Nutov: Improved approximation algorithms for directed steiner forest. Journal of Computer and System Sciences, 78(1):279–292, 2012. [doi:10.1016/j.jcss.2011.05.009]

[47]   Manuel Fernández V, David P Woodruff, and Taisuke Yasuda: Graph spanners in the message-passing model. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.77]

[48]   Arnold Filtser, Michael Kapralov, and Navid Nouri: Graph spanners by sketching in dynamic streams and the simultaneous communication model. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1894–1913. SIAM, 2021. [doi:10.1137/1.9781611976465.11]

[49]   Lisa Fleischer, Jochen Könemann, Stefano Leonardi, and Guido Schäfer: Simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 663–670, 2006. [doi:10.1145/1132516.1132609]

[50]    Naveen Garg, Goran Konjevod, and Ramamoorthi Ravi: A polylogarithmic approximation algorithm for the group steiner tree problem. Journal of Algorithms, 37(1):66–84, 2000. [doi:10.1006/jagm.2000.1096]

[51]   Michel X. Goemans and David P. Williamson: A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296–317, 1995. [doi:10.1137/S0097539793242618]

[52]   Elena Grigorescu, Young-San Lin, and Kent Quanrud: Online directed spanners and steiner forests. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2021. [doi:10.4230/LIPIcs.APPROX/RANDOM.2021.5]

[53]   Anupam Gupta, Amit Kumar, Martin Pál, and Tim Roughgarden: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), pp. 606–615. IEEE, 2003. [doi:10.1109/SFCS.2003.1238233]

[54]   Anupam Gupta and Viswanath Nagarajan: Approximating sparse covering integer programs online. Mathematics of Operations Research, 39(4):998–1011, 2014. [doi:10.1287/moor.2014.0652]

[55]   Anupam Gupta, R Ravi, Kunal Talwar, and Seeun William Umboh: Last but not least: Online spanners for buy-at-bulk. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 589–599. SIAM, 2017. [doi:10.1137/1.9781611974782.38]

[56]   Anupam Gupta, Kunal Talwar, and Udi Wieder: Changing bases: Multistage optimization for matroids and matchings. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pp. 563–575. Springer, 2014. [doi:10.1007/978-3-662-43948-7_47]

[57]   Refael Hassin: Approximation schemes for the restricted shortest path problem. Mathematics of Operations research, 17(1):36–42, 1992. [doi:10.1287/moor.17.1.36]

[58]   Christopher S Helvig, Gabriel Robins, and Alexander Zelikovsky: An improved approximation scheme for the group steiner problem. Networks: An International Journal, 37(1):8–20, 2001. [doi:10.1002/1097-0037(200101)37:1¡8::AID-NET2¿3.0.CO;2-R]

[59]   Makoto Imase and Bernard M Waxman: Dynamic steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369–384, 1991. [doi:10.1137/0404033]

[60]   Michael Kapralov and David P. Woodruff: Spanners and sparsifiers in dynamic streams. In Magnús M. Halldórsson and Shlomi Dolev, editors, Proceedings of the 33rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 272–281. ACM, 2014. [doi:10.1145/2611462.2611497]

[61]   Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan S. Owicki: Competitive randomized algorithms for non-uniform problems. Algorithmica, 11(6):542–571, 1994. [doi:10.1007/BF01189993]

[62]   Vikram Khurana, Jian Peng, Chee Yeun Chung, Pavan K Auluck, Saranna Fanning, Daniel F Tardiff, Theresa Bartels, Martina Koeva, Stephen W Eichhorn, Hadar Benyamini, et al.: Genome-scale networks link neurodegenerative disease genes to α-synuclein through specific molecular pathways. Cell systems, 4(2):157–170, 2017. [doi:10.1016/j.cels.2016.12.011]

[63]   Jochen Könemann, Stefano Leonardi, Guido Schäfer, and Stefan van Zwam: From primal-dual to cost shares and back: a stronger lp relaxation for the steiner forest problem. In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 930–942. Springer, 2005. [doi:10.1007/11523468_75]

[64]   Jochen Könemann, Stefano Leonardi, Guido Schäfer, and Stefan HM van Zwam: A group-strategyproof cost sharing mechanism for the steiner forest game. SIAM Journal on Computing, 37(5):1319–1341, 2008. [doi:10.1137/050646408]

[65]   Guy Kortsarz: On the hardness of approximating spanners. Algorithmica, 30:432–450, 2001. [doi:10.1007/s00453-001-0021-y]

[66]   Dean H Lorenz and Danny Raz: A simple efficient approximation scheme for the restricted shortest path problem. Operations Research Letters, 28(5):213–219, 2001. [doi:10.1016/S0167-6377(01)00069-4]

[67]   Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, and Virginia Vassilevska Williams: Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1374–1392. SIAM, 2018. [doi:10.1137/1.9781611975031.91]

[68]   Mihai Patrascu and Liam Roditty: Distance oracles beyond the Thorup-Zwick bound. SIAM Journal on Computing, 43(1):300–311, 2014. [doi:10.1137/11084128X]

[69]   David Peleg and Alejandro A. Schäffer: Graph spanners. Journal of Graph Theory, 13(1):99–116, 1989. [doi:10.1002/jgt.3190130114]

[70]   David Peleg and Jeffrey D. Ullman: An optimal synchronizer for the hypercube. SIAM Journal on Computing, 18(4):740–747, 1989. [doi:10.1137/0218050]

[71]   Leila Pirhaji, Pamela Milani, Mathias Leidl, Timothy Curran, Julian Avila-Pacheco, Clary B Clish, Forest M White, Alan Saghatelian, and Ernest Fraenkel: Revealing disease-associated pathways by network integration of untargeted metabolomics. Nature methods, 13(9):770–776, 2016. [doi:10.1038/nmeth.3940]

[72]   Iam Roditty, Mikkel Thorup, and Uri Zwick: Roundtrip spanners and roundtrip routing in directed graphs. ACM Transactions on Algorithms (TALG), 4(3):1–17, 2008. [doi:10.1145/1367064.1367069]

[73]   Tim Roughgarden and Mukund Sundararajan: Optimal efficiency guarantees for network design mechanisms. In Proceedings of the 8th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 469–483. Springer, 2007. [doi:10.1007/978-3-540-72792-7_35]

[74]   Xiangkun Shen and Viswanath Nagarajan: Online covering with ℓq-norm objectives and applications to network design. Mathematical Programming, 184, 2020. [doi:10.1007/s10107-019-01409-9]

[75]   Andrew Chi-Chih Yao: Space-time tradeoff for answering range queries (extended abstract). In Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC), 1982. [doi:10.1145/800070.802185]

[76]   Neal Young: The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525–541, 1994. [doi:10.1007/BF01189992]

[77]   Alexander Zelikovsky: A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica, 18(1):99–110, 1997. [doi:10.1007/BF02523690]