Files in this item

FilesDescriptionFormat

application/pdf

application/pdfAli_Vakilian.pdf (614kB)
(no description provided)PDF

application/zip

application/zipfigures.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


This item appears in the following Collection(s)

Item Statistics