Node-weighted prize-collecting survivable network design problems

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 π(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⁴ \log² n)-approximation for PC-VC-SNDP which improves to O(k⁴ \log n) on instances from a minor-closed families of graphs.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2013

Author dc:creator

• Vakilian, Ali

Contributors dc:contributor

• Chekuri, Chandra S.

• Approximation Algorithm
• Survivable Network Design
• Steiner Network
• Prize-collecting survivable network design problem (SNDP)

Statement dc:rights

• Copyright 2013 Ali Vakilian

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/45452

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/45452