Survivable network design problems with element and vertex connectivity requirements

Approximation algorithm;Network design;Bounded degree;Iterative rounding;Element connectivity;Node connectivity

Patwa, Shweta Jayant ; Chekuri ; Chandra

关键词: Approximation algorithm;    Network design;    Bounded degree;    Iterative rounding;    Element connectivity;    Node connectivity;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/98117/PATWA-THESIS-2017.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.