{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T11:28:15Z","timestamp":1764588495911,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031498145"},{"type":"electronic","value":"9783031498152"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-49815-2_14","type":"book-chapter","created":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T07:02:28Z","timestamp":1703142148000},"page":"190-204","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved Approximations for\u00a0Relative Survivable Network Design"],"prefix":"10.1007","author":[{"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[]},{"given":"Ama","family":"Koranteng","sequence":"additional","affiliation":[]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[]},{"given":"Zeev","family":"Nutov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,22]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D., Hommelsheim, F., M\u00fchlenthaler, M.: Flexible graph connectivity: approximating network design problems between 1- and 2-connectivity (2020)","DOI":"10.1007\/s10107-021-01664-9"},{"key":"14_CR2","unstructured":"Adjiashvili, D., Hommelsheim, F., M\u00fchlenthaler, M., Schaudt, O.: Fault-tolerant edge-disjoint paths - beyond uniform faults (2020)"},{"key":"14_CR3","unstructured":"Bansal, I., Cheriyan, J., Grout, L., Ibrahimpur, S.: Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions (2022)"},{"key":"14_CR4","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Multiple-edge-fault-tolerant approximate shortest-path trees (2016). https:\/\/doi.org\/10.48550\/ARXIV.1601.04169","DOI":"10.48550\/ARXIV.1601.04169"},{"key":"14_CR5","doi-asserted-by":"publisher","unstructured":"Bodwin, G., Dinitz, M., Nazari, Y.: Vertex fault-tolerant emulators. In: Braverman, M. (ed.) 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. LIPIcs, vol. 215, pp. 25:1\u201325:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2022.25","DOI":"10.4230\/LIPIcs.ITCS.2022.25"},{"key":"14_CR6","unstructured":"Bodwin, G., Dinitz, M., Nazari, Y.: Epic fail: emulators can tolerate polynomially many edge faults for free. In: 14th Innovations in Theoretical Computer Science Conference, ITCS 2023 (2023)"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Bodwin, G., Dinitz, M., Parter, M., Williams, V.V.: Optimal vertex fault tolerant spanners (for fixed stretch). In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7\u201310 January 2018, pp. 1884\u20131900. SIAM (2018)","DOI":"10.1137\/1.9781611975031.123"},{"key":"14_CR8","doi-asserted-by":"publisher","unstructured":"Bodwin, G., Dinitz, M., Robelle, C.: Optimal vertex fault-tolerant spanners in polynomial time. In: Naor, J.S., Buchbinder, N. (eds.) Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pp. 2924\u20132938. SIAM (2022). https:\/\/doi.org\/10.1137\/1.9781611976465.174","DOI":"10.1137\/1.9781611976465.174"},{"key":"14_CR9","doi-asserted-by":"publisher","unstructured":"Bodwin, G., Patel, S.: A trivial yet optimal solution to vertex fault tolerant spanners. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, pp. 541\u2013543. Association for Computing Machinery, New York (2019). https:\/\/doi.org\/10.1145\/3293611.3331588","DOI":"10.1145\/3293611.3331588"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Boyd, S., Cheriyan, J., Haddadan, A., Ibrahimpur, S.: Approximation algorithms for flexible graph connectivity (2022)","DOI":"10.1007\/s10107-023-01961-5"},{"issue":"7","key":"14_CR11","doi-asserted-by":"publisher","first-page":"3403","DOI":"10.1137\/090758039","volume":"39","author":"S Chechik","year":"2010","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault tolerant spanners for general graphs. SIAM J. Comput. 39(7), 3403\u20133423 (2010)","journal-title":"SIAM J. Comput."},{"key":"14_CR12","unstructured":"Chekuri, C., Jain, R.: Approximating flexible graph connectivity via r\u00e4cke tree based rounding (2022)"},{"key":"14_CR13","unstructured":"Chekuri, C., Jain, R.: Augmentation based approximation algorithms for flexible network design (2022)"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Laekhanukit, B., Naves, G., Vetta, A.: Approximating rooted Steiner networks. ACM Trans. Algorithms 11(2), 8:1\u20138:22 (2014)","DOI":"10.1145\/2650183"},{"issue":"2","key":"14_CR15","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J Cheriyan","year":"2000","unstructured":"Cheriyan, J., Thurimella, R.: Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput. 30(2), 528\u2013560 (2000). https:\/\/doi.org\/10.1137\/S009753979833920X","journal-title":"SIAM J. Comput."},{"key":"14_CR16","unstructured":"Dinitz, M., Koranteng, A., Kortsarz, G.: Relative survivable network design. In: APPROX-RANDOM, vol. 245, pp. 41:1\u201341:19 (2022)"},{"key":"14_CR17","doi-asserted-by":"publisher","unstructured":"Dinitz, M., Koranteng, A., Kortsarz, G., Nutov, Z.: Improved approximations for relative survivable network design (2023). https:\/\/doi.org\/10.48550\/arXiv.2304.06656","DOI":"10.48550\/arXiv.2304.06656"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, 6\u20138 June 2011, pp. 169\u2013178 (2011)","DOI":"10.1145\/1993806.1993830"},{"key":"14_CR19","doi-asserted-by":"publisher","unstructured":"Dinitz, M., Robelle, C.: Efficient and simple algorithms for fault-tolerant spanners. In: Emek, Y., Cachin, C. (eds.) ACM Symposium on Principles of Distributed Computing, PODC 2020, pp. 493\u2013500. ACM (2020). https:\/\/doi.org\/10.1145\/3382734.3405735","DOI":"10.1145\/3382734.3405735"},{"key":"14_CR20","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/PL00009195","volume":"20","author":"Y Dinitz","year":"1998","unstructured":"Dinitz, Y., Westbrook, J.: Maintaining the classes of 4-edge-connectivity in a graph on-line. Algorithmica 20, 242\u2013276 (1998)","journal-title":"Algorithmica"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Dinitz, Y., Nutov, Z.: A 2-level cactus model for the system of minimum and minimum+ 1 edge-cuts in a graph and its incremental maintenance. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 509\u2013518 (1995)","DOI":"10.1145\/225058.225268"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Feldmann, A.E., Mukherjee, A., van Leeuwen, E.J.: The parameterized complexity of the survivable network design problem. In: SOSA, pp. 37\u201356 (2022)","DOI":"10.1137\/1.9781611977066.4"},{"issue":"4","key":"14_CR23","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/net.20289","volume":"53","author":"HN Gabow","year":"2009","unstructured":"Gabow, H.N., Goemans, M.X., Tardos, \u00c9., Williamson, D.P.: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks 53(4), 345\u2013357 (2009)","journal-title":"Networks"},{"issue":"1","key":"14_CR24","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1006\/jagm.1997.0855","volume":"24","author":"MR Henzinger","year":"1997","unstructured":"Henzinger, M.R.: A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. J. Algorithms 24(1), 194\u2013220 (1997)","journal-title":"J. Algorithms"},{"issue":"1","key":"14_CR25","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39\u201360 (2001). https:\/\/doi.org\/10.1007\/s004930170004","journal-title":"Combinatorica"},{"key":"14_CR26","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.tcs.2011.08.021","volume":"416","author":"R Khandekar","year":"2012","unstructured":"Khandekar, R., Kortsarz, G., Nutov, Z.: Approximating fault-tolerant Group-Steiner problems. Theor. Comput. Sci. 416, 55\u201364 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR27","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/j.dam.2020.03.046","volume":"303","author":"OS Lo","year":"2021","unstructured":"Lo, O.S., Schmidt, J.M., Thorup, M.: Compact cactus representations of all non-trivial min-cuts. Discret. Appl. Math. 303, 296\u2013304 (2021)","journal-title":"Discret. Appl. Math."},{"key":"14_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-642-25870-1_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D Marx","year":"2011","unstructured":"Marx, D.: Important separators and parameterized algorithms. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 5\u201310. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-25870-1_2"},{"issue":"5","key":"14_CR29","doi-asserted-by":"publisher","first-page":"1521","DOI":"10.1137\/S0097539793257770","volume":"29","author":"JAL Poutre","year":"2000","unstructured":"Poutre, J.A.L.: Maintenance of 2- and 3-edge-connected components of graphs II. SIAM J. Comput. 29(5), 1521\u20131549 (2000)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"14_CR30","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF01299747","volume":"15","author":"DP Williamson","year":"1995","unstructured":"Williamson, D.P., Goemans, M.X., Mihail, M., Vazirani, V.V.: A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica 15(3), 435\u2013454 (1995). https:\/\/doi.org\/10.1007\/BF01299747","journal-title":"Combinatorica"}],"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-031-49815-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T07:04:05Z","timestamp":1703142245000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49815-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031498145","9783031498152"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49815-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"22 December 2023","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":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2023\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"16","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.05","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7.7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}