{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/98117"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/98117","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Survivable network design problems with element and vertex connectivity requirements","abstract":"In this thesis, we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The algorithm follows the iterated rounding framework that has been used for these problems over the past many years. This can be achieved by adding a restriction on which edges can be added to the solution in any iteration of the iterated rounding algorithm. We wanted to investigate this approach in the context of degree-bounded Elem-SNDP and degree-bounded Rooted k-outconnectivity because it helped simplify the proof idea for edge-connectivity SNDP (EC-SNDP), while achieving approximation ratios that were as good as the best known result. Given a graph G=(V,E) with costs on edges, connectivity requirements between pairs of vertices and degree constraints on vertices, the goal is to compute a minimum cost subgraph H of G that obeys the connectivity requirements and satisfies the degree bounds on the vertices. In the case of element connectivity, connectivity requirement r(uv) between vertices u and v represents the required number of element-disjoint paths between the two vertices. The elements are made up of all the edges and unreliable vertices. This way of defining connectivity models networks where links and nodes can both fail. For Elem-SNDP, our algorithm outputs a solution that has cost at most 3OPT and the degree on each vertex v in the solution is at most 19b(v)+7. In the context of rooted k-outconnectivity problem, connectivity requirement represents the number of internally vertex-disjoint paths between vertices the root r and a vertex v. We extend our approach for Elem-SNDP to the degree-bounded Rooted k-outconnectivity problem. Our algorithm for the latter computes a solution that has cost at most 3OPT and the out-degree on each vertex v in the solution is 19b^+(v)+7. In addition, the in-degree of vertex v is bounded above by b^-(v)+5.","abstract_html":"In this thesis, we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The algorithm follows the iterated rounding framework that has been used for these problems over the past many years. This can be achieved by adding a restriction on which edges can be added to the solution in any iteration of the iterated rounding algorithm. We wanted to investigate this approach in the context of degree-bounded Elem-SNDP and degree-bounded Rooted k-outconnectivity because it helped simplify the proof idea for edge-connectivity SNDP (EC-SNDP), while achieving approximation ratios that were as good as the best known result. Given a graph G=(V,E) with costs on edges, connectivity requirements between pairs of vertices and degree constraints on vertices, the goal is to compute a minimum cost subgraph H of G that obeys the connectivity requirements and satisfies the degree bounds on the vertices. In the case of element connectivity, connectivity requirement r(uv) between vertices u and v represents the required number of element-disjoint paths between the two vertices. The elements are made up of all the edges and unreliable vertices. This way of defining connectivity models networks where links and nodes can both fail. For Elem-SNDP, our algorithm outputs a solution that has cost at most 3OPT and the degree on each vertex v in the solution is at most 19b(v)+7. In the context of rooted k-outconnectivity problem, connectivity requirement represents the number of internally vertex-disjoint paths between vertices the root r and a vertex v. We extend our approach for Elem-SNDP to the degree-bounded Rooted k-outconnectivity problem. Our algorithm for the latter computes a solution that has cost at most 3OPT and the out-degree on each vertex v in the solution is 19b^+(v)+7. In addition, the in-degree of vertex v is bounded above by b^-(v)+5.","abstract_has_math":false,"creators":["Patwa, Shweta Jayant"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chekuri, Chandra"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-09-29T16:37:56Z","date_published":"2017-09-29T16:37:56Z","updated_at":"2026-07-22T22:24:34Z","subjects":["Approximation algorithm","Network design","Bounded degree","Iterative rounding","Element connectivity","Node connectivity"],"languages":["en"],"rights":["Copyright 2017 Shweta Jayant Patwa"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/98117","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chekuri, Chandra"]},{"key":"dc:creator","label":"Author","values":["Patwa, Shweta Jayant"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-09-29T16:37:56Z","2017-06-14","2017-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Approximation algorithm","Network design","Bounded degree","Iterative rounding","Element connectivity","Node connectivity"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Shweta Jayant Patwa"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/98117"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The algorithm follows the iterated rounding framework that has been used for these problems over the past many years. This can be achieved by adding a restriction on which edges can be added to the solution in any iteration of the iterated rounding algorithm. We wanted to investigate this approach in the context of degree-bounded Elem-SNDP and degree-bounded Rooted k-outconnectivity because it helped simplify the proof idea for edge-connectivity SNDP (EC-SNDP), while achieving approximation ratios that were as good as the best known result. Given a graph G=(V,E) with costs on edges, connectivity requirements between pairs of vertices and degree constraints on vertices, the goal is to compute a minimum cost subgraph H of G that obeys the connectivity requirements and satisfies the degree bounds on the vertices. In the case of element connectivity, connectivity requirement r(uv) between vertices u and v represents the required number of element-disjoint paths between the two vertices. The elements are made up of all the edges and unreliable vertices. This way of defining connectivity models networks where links and nodes can both fail. For Elem-SNDP, our algorithm outputs a solution that has cost at most 3OPT and the degree on each vertex v in the solution is at most 19b(v)+7. In the context of rooted k-outconnectivity problem, connectivity requirement represents the number of internally vertex-disjoint paths between vertices the root r and a vertex v. We extend our approach for Elem-SNDP to the degree-bounded Rooted k-outconnectivity problem. Our algorithm for the latter computes a solution that has cost at most 3OPT and the out-degree on each vertex v in the solution is 19b^+(v)+7. In addition, the in-degree of vertex v is bounded above by b^-(v)+5.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo terms","The student, Shweta Patwa, accepted the attached license on 2017-06-14 at 09:48.","The student, Shweta Patwa, submitted this Thesis for approval on 2017-06-14 at 10:17.","This Thesis was approved for publication on 2017-06-14 at 16:05.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11218 on 2017-09-29 at 11:26:41","Made available in DSpace on 2017-09-29T16:37:56Z (GMT). No. of bitstreams: 2 PATWA-THESIS-2017.pdf: 734395 bytes, checksum: d54d7909e2c21ceb2b5033eb7d3de4b3 (MD5) LICENSE.txt: 4209 bytes, checksum: f98b3c466642a0742a2be9a478aea570 (MD5) Previous issue date: 2017-06-14"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Survivable network design problems with element and vertex connectivity requirements"]}]}],"canonical_facts":{"dc:contributor":["Chekuri, Chandra"],"dc:creator":["Patwa, Shweta Jayant"],"dc:date":["2017-09-29T16:37:56Z","2017-06-14","2017-08"],"dc:description":["In this thesis, we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The algorithm follows the iterated rounding framework that has been used for these problems over the past many years. This can be achieved by adding a restriction on which edges can be added to the solution in any iteration of the iterated rounding algorithm. We wanted to investigate this approach in the context of degree-bounded Elem-SNDP and degree-bounded Rooted k-outconnectivity because it helped simplify the proof idea for edge-connectivity SNDP (EC-SNDP), while achieving approximation ratios that were as good as the best known result. Given a graph G=(V,E) with costs on edges, connectivity requirements between pairs of vertices and degree constraints on vertices, the goal is to compute a minimum cost subgraph H of G that obeys the connectivity requirements and satisfies the degree bounds on the vertices. In the case of element connectivity, connectivity requirement r(uv) between vertices u and v represents the required number of element-disjoint paths between the two vertices. The elements are made up of all the edges and unreliable vertices. This way of defining connectivity models networks where links and nodes can both fail. For Elem-SNDP, our algorithm outputs a solution that has cost at most 3OPT and the degree on each vertex v in the solution is at most 19b(v)+7. In the context of rooted k-outconnectivity problem, connectivity requirement represents the number of internally vertex-disjoint paths between vertices the root r and a vertex v. We extend our approach for Elem-SNDP to the degree-bounded Rooted k-outconnectivity problem. Our algorithm for the latter computes a solution that has cost at most 3OPT and the out-degree on each vertex v in the solution is 19b^+(v)+7. In addition, the in-degree of vertex v is bounded above by b^-(v)+5.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo terms","The student, Shweta Patwa, accepted the attached license on 2017-06-14 at 09:48.","The student, Shweta Patwa, submitted this Thesis for approval on 2017-06-14 at 10:17.","This Thesis was approved for publication on 2017-06-14 at 16:05.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11218 on 2017-09-29 at 11:26:41","Made available in DSpace on 2017-09-29T16:37:56Z (GMT). No. of bitstreams: 2 PATWA-THESIS-2017.pdf: 734395 bytes, checksum: d54d7909e2c21ceb2b5033eb7d3de4b3 (MD5) LICENSE.txt: 4209 bytes, checksum: f98b3c466642a0742a2be9a478aea570 (MD5) Previous issue date: 2017-06-14"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/98117"],"dc:language":["en"],"dc:rights":["Copyright 2017 Shweta Jayant Patwa"],"dc:subject":["Approximation algorithm","Network design","Bounded degree","Iterative rounding","Element connectivity","Node connectivity"],"dc:title":["Survivable network design problems with element and vertex connectivity requirements"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:34Z"}