## Files in this item

FilesDescriptionFormat

application/pdf

Ali_Vakilian.pdf (614kB)
(no description provided)PDF

application/zip

figures.zip (125kB)
(no description provided)ZIP

## Description

 Title: Node-weighted prize-collecting 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 Urbana-Champaign Degree: M.S. Genre: Thesis Subject(s): Approximation Algorithm Survivable Network Design Steiner Network Prize-collecting survivable network design problem (SNDP) Abstract: We consider node-weighted network design problems, in particular the survivable network design problem SNDP and its prize-collecting version PC-SNDP. The input consists of a node-weighted undirected graph $G=(V,E)$ and integral connectivity requirements $r(st)$ for each pair of nodes $st$. The goal is to find a minimum node-weighted subgraph $H$ of $G$ such that, for each pair $st$, $H$ contains $r(st)$ \emph{disjoint} paths between $s$ and $t$. PC-SNDP 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{edge-connectivity (EC)}, \emph{element-connectivity (ELC)} and \emph{vertex-connectivity (VC)}. Let $k = \max_{st} r(st)$ be the maximum requirement. There has been no non-trivial approximation for node-weighted PC-SNDP for $k > 1$ even in edge-connectivity setup. We describe multiroute-flow based relaxations for PC-EC-SNDP and PC-ELC-SNDP and obtain approximation algorithms for PC-SNDP and PC-ELC-SNDP through them. The approximation ratios we obtain for PC-EC-SNDP are similar to those that were previously known for EC-SNDP via combinatorial algorithms. Specifically, for PC-EC-SNDP (and PC-ELC-SNDP) 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 ELC-SNDP and the reduction method of Chuzhoy and Khanna~\cite{ChuzhoyK12} we obtain $O(k^4 \log^2 n)$-approximation for PC-VC-SNDP which improves to $O(k^4 \log n)$ on instances from a minor-closed families of graphs. Issue Date: 2013-08-22 URI: http://hdl.handle.net/2142/45452 Rights Information: Copyright 2013 Ali Vakilian Date Available in IDEALS: 2013-08-22 Date Deposited: 2013-08
﻿