Files in this item
Files  Description  Format 

application/pdf Ali_Vakilian.pdf (614kB)  (no description provided)  
application/zip figures.zip (125kB)  (no description provided)  ZIP 
Description
Title:  Nodeweighted prizecollecting survivable network design problems 
Author(s):  Vakilian, Ali 
Advisor(s):  Chekuri, Chandra S. 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  M.S. 
Genre:  Thesis 
Subject(s):  Approximation Algorithm
Survivable Network Design Steiner Network Prizecollecting survivable network design problem (SNDP) 
Abstract:  We consider nodeweighted network design problems, in particular the survivable network design problem SNDP and its prizecollecting version PCSNDP. The input consists of a nodeweighted undirected graph $G=(V,E)$ and integral connectivity requirements $r(st)$ for each pair of nodes $st$. The goal is to find a minimum nodeweighted subgraph $H$ of $G$ such that, for each pair $st$, $H$ contains $r(st)$ \emph{disjoint} paths between $s$ and $t$. PCSNDP is a generalization in which the input also includes a penalty $\pi(st)$ for each pair, and the goal is to find a subgraph $H$ to minimize the sum of the weight of $H$ and the sum of the penalties for all pairs whose connectivity requirements are not fully satisfied by $H$. We consider three types of connectivity requirements, \emph{edgeconnectivity (EC)}, \emph{elementconnectivity (ELC)} and \emph{vertexconnectivity (VC)}. Let $k = \max_{st} r(st)$ be the maximum requirement. There has been no nontrivial approximation for nodeweighted PCSNDP for $k > 1$ even in edgeconnectivity setup. We describe multirouteflow based relaxations for PCECSNDP and PCELCSNDP and obtain approximation algorithms for PCSNDP and PCELCSNDP through them. The approximation ratios we obtain for PCECSNDP are similar to those that were previously known for ECSNDP via combinatorial algorithms. Specifically, for PCECSNDP (and PCELCSNDP) we obtain an $O(k \log n)$approximation in general graphs and an $O(k)$approximation in graphs that exclude a fixed minor. Moreover, based on the approximation algorithm of ELCSNDP and the reduction method of Chuzhoy and Khanna~\cite{ChuzhoyK12} we obtain $O(k^4 \log^2 n)$approximation for PCVCSNDP which improves to $O(k^4 \log n)$ on instances from a minorclosed families of graphs. 
Issue Date:  20130822 
URI:  http://hdl.handle.net/2142/45452 
Rights Information:  Copyright 2013 Ali Vakilian 
Date Available in IDEALS:  20130822 
Date Deposited:  201308 
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