Files in this item
Files  Description  Format 

application/pdf PATWATHESIS2017.pdf (734kB)  (no description provided) 
Description
Title:  Survivable network design problems with element and vertex connectivity requirements 
Author(s):  Patwa, Shweta Jayant 
Advisor(s):  Chekuri, Chandra 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  M.S. 
Genre:  Thesis 
Subject(s):  Approximation algorithm
Network design Bounded degree Iterative rounding Element connectivity Node connectivity 
Abstract:  In this thesis, we consider degreebounded elementconnectivity Survivable Network Design Problem (ElemSNDP) and degreebounded Rooted koutconnectivity 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 degreebounded ElemSNDP and degreebounded Rooted koutconnectivity because it helped simplify the proof idea for edgeconnectivity SNDP (ECSNDP), 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 elementdisjoint 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 ElemSNDP, 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 koutconnectivity problem, connectivity requirement represents the number of internally vertexdisjoint paths between vertices the root r and a vertex v. We extend our approach for ElemSNDP to the degreebounded Rooted koutconnectivity problem. Our algorithm for the latter computes a solution that has cost at most 3OPT and the outdegree on each vertex v in the solution is 19b^+(v)+7. In addition, the indegree of vertex v is bounded above by b^(v)+5. 
Issue Date:  20170614 
Type:  Text 
URI:  http://hdl.handle.net/2142/98117 
Rights Information:  Copyright 2017 Shweta Jayant Patwa 
Date Available in IDEALS:  20170929 
Date Deposited:  201708 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois