{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T19:25:21Z","timestamp":1768591521511,"version":"3.49.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032067050","type":"print"},{"value":"9783032067067","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-06706-7_4","type":"book-chapter","created":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T23:57:51Z","timestamp":1759276671000},"page":"48-63","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Simple Approximations for\u00a0General Spanner Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7950-6965","authenticated-orcid":false,"given":"Fritz","family":"B\u00f6kler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4681-5550","authenticated-orcid":false,"given":"Markus","family":"Chimani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9821-8600","authenticated-orcid":false,"given":"Henning","family":"Jasper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,1]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Ahmed, R., et al.: Graph spanners: a tutorial review. Comput. Sci. Rev. 37 (2020)","DOI":"10.1016\/j.cosrev.2020.100253"},{"issue":"1","key":"4_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"4_CR3","unstructured":"Archambault, D., Liotta, G., N\u00f6llenburg, M., Piselli, T., Tappini, A., Wallinger, M.: Bundling-aware graph drawing. In: GD 2024, vol.\u00a0320, pp. 15:1\u201315:19 (2024)"},{"key":"4_CR4","unstructured":"B\u00f6kler, F., Chimani, M., Jasper, H., Wagner, M.H.: Exact minimum weight spanners via column generation. In: ESA 2024. LIPIcs, vol. 308, pp. 30:1\u201330:17 (2024)"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6kler, F., Chimani, M., Jasper, H.: Simple approximations for general spanner problems (2025). https:\/\/arxiv.org\/abs\/2506.23638","DOI":"10.1007\/978-3-032-06706-7_4"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. In: SoCG 1992, pp. 192\u2013201. ACM (1992)","DOI":"10.1145\/142675.142717"},{"issue":"5","key":"4_CR7","doi-asserted-by":"publisher","first-page":"1772","DOI":"10.1137\/090750317","volume":"39","author":"C Chekuri","year":"2010","unstructured":"Chekuri, C., Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R.: Approximation algorithms for nonuniform buy-at-bulk network design. SIAM J. Comput. 39(5), 1772\u20131798 (2010)","journal-title":"SIAM J. Comput."},{"key":"4_CR8","unstructured":"Chimani, M., Spoerhase, J.: Network design problems with bounded distances via shallow-light Steiner trees. In: STACS 2015. LIPIcs, vol. 30, pp. 238\u2013248 (2015)"},{"key":"4_CR9","unstructured":"Chimani, M., Stutzenstein, F.: Spanner approximations in practice. In: ESA 2022. LIPIcs, vol. 244, pp. 37:1\u201337:15 (2022)"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Chlamt\u00e1\u010d, E., Dinitz, M., Kortsarz, G., Laekhanukit, B.: Approximating spanners and directed Steiner forest: upper and lower bounds. ACM Trans. Algorithms 16(3) (2020)","DOI":"10.1145\/3381451"},{"issue":"2","key":"4_CR11","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1137\/050630696","volume":"20","author":"D Coppersmith","year":"2006","unstructured":"Coppersmith, D., Elkin, M.: Sparse sourcewise and pairwise distance preservers. SIAM J. Discret. Math. 20(2), 463\u2013501 (2006)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"4_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2818375","volume":"12","author":"M Dinitz","year":"2015","unstructured":"Dinitz, M., Kortsarz, G., Raz, R.: Label cover instances with large girth and the hardness of approximating basic k-spanner. ACM Trans. Algorithms 12(2), 1\u201316 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Directed spanners via flow-based linear programs. In: STOC 2011, pp. 323\u2013332. ACM (2011)","DOI":"10.1145\/1993636.1993680"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Khanna, S.: Design networks with bounded pairwise distance. In: STOC 1999, pp. 750\u2013759. ACM (1999)","DOI":"10.1145\/301250.301447"},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"1312","DOI":"10.1137\/140979538","volume":"29","author":"M Elkin","year":"2015","unstructured":"Elkin, M., Neiman, O., Solomon, S.: Light spanners. SIAM J. Discret. Math. 29(3), 1312\u20131321 (2015)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"4_CR16","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)","journal-title":"Theory Comput. Syst."},{"key":"4_CR17","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Company, New York (1979)"},{"issue":"1","key":"4_CR18","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N Garg","year":"2000","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37(1), 66\u201384 (2000)","journal-title":"J. Algorithms"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"113691","DOI":"10.1016\/j.tcs.2023.113691","volume":"947","author":"R G\u00f3mez","year":"2023","unstructured":"G\u00f3mez, R., Miyazawa, F.K., Wakabayashi, Y.: Improved NP-hardness results for the minimum t-spanner problem on bounded-degree graphs. Theoret. Comput. Sci. 947, 113691 (2023)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR20","unstructured":"Grigorescu, E., Kumar, N., Lin, Y.S.: Approximation algorithms for directed weighted spanners. In: APPROX\/RANDOM 2023. LIPIcs, vol. 275, pp. 8:1\u20138:23 (2023)"},{"key":"4_CR21","unstructured":"Heinrich, I., Herrala, O., Schiewe, P., Terho, T.: Using light spanning graphs for passenger assignment in public transport. In: ATMOS 2023. OASIcs, vol. 115, pp. 2:1\u20132:16 (2023)"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-319-08404-6_24","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"MBT Knudsen","year":"2014","unstructured":"Knudsen, M.B.T.: Additive spanners: a simple construction. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 277\u2013281. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-08404-6_24"},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/s00453-001-0021-y","volume":"30","author":"G Kortsarz","year":"2001","unstructured":"Kortsarz, G.: On the hardness of approximating spanners. Algorithmica 30, 432\u2013450 (2001)","journal-title":"Algorithmica"},{"issue":"2","key":"4_CR24","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1006\/jagm.1994.1032","volume":"17","author":"G Kortsarz","year":"1994","unstructured":"Kortsarz, G., Peleg, D.: Generating sparse 2-spanners. J. Algorithms 17(2), 222\u2013236 (1994)","journal-title":"J. Algorithms"},{"issue":"5","key":"4_CR25","first-page":"213","volume":"28","author":"DH Lorenz","year":"2001","unstructured":"Lorenz, D.H., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. OPERRL 28(5), 213\u2013219 (2001)","journal-title":"OPERRL"},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/3-540-46784-X_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D Peleg","year":"1999","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, pp. 30\u201341. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-46784-X_5"},{"issue":"1","key":"4_CR27","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.: Graph spanners. J. Graph Theory 13(1), 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1007\/978-3-540-30140-0_70","volume-title":"Algorithms \u2013 ESA 2004","author":"M Sigurd","year":"2004","unstructured":"Sigurd, M., Zachariasen, M.: Construction of minimum-weight spanners. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 797\u2013808. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30140-0_70"},{"key":"4_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-319-90530-3_26","volume-title":"Computer Science \u2013 Theory and Applications","author":"D Wojtczak","year":"2018","unstructured":"Wojtczak, D.: On strong NP-completeness of rational problems. In: Fomin, F.V., Podolskii, V.V. (eds.) CSR 2018. LNCS, vol. 10846, pp. 308\u2013320. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-90530-3_26"},{"key":"4_CR30","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: Lower bounds for additive spanners, emulators, and more. In: IEEE FOCS 2006, pp. 389\u2013398. IEEE (2006)","DOI":"10.1109\/FOCS.2006.45"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-06706-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T07:09:04Z","timestamp":1768547344000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-06706-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,1]]},"ISBN":["9783032067050","9783032067067"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-06706-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,1]]},"assertion":[{"value":"1 October 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2025\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}