Node-weighted prize-collecting survivable network design problems

Vakilian, Ali

Permalink

https://hdl.handle.net/2142/45452 Copy

Description

Title

Node-weighted prize-collecting survivable network design problems

Author(s)

Vakilian, Ali

Issue Date

2013-08-22T16:40:35Z

Director of Research (if dissertation) or Advisor (if thesis)

Chekuri, Chandra S.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(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.

Graduation Semester

2013-08

Permalink

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

Copyright and License Information

Copyright 2013 Ali Vakilian

Owning Collections