2026-09-19T15:42:15Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/45452 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Chekuri, Chandra S. Vakilian, Ali 2013-08-22T16:40:35Z 2013-08-22T16:40:35Z 2013-08 2013-08-22T16:40:35Z 2013-08 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. Item withdrawn by Alexis Thompson (athmpsn1@illinois.edu) on 2013-07-11T20:48:56Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 5 nw-pc-sndp-thesis.pdf: 614134 bytes, checksum: 823576f4e0fc535fe06af2f3b7c89bc0 (MD5) ms_thesis.bib: 13403 bytes, checksum: d2f7f0fabda6c5947dc32c1dfad862c6 (MD5) nw-pc-sndp-thesis.tex: 166441 bytes, checksum: bf19e9e3ba79a53f273b70189ead566c (MD5) figures.zip: 124579 bytes, checksum: 37c7cb93fa408c51336e23a2948773a3 (MD5) Vakilian_Ali.pdf: 614134 bytes, checksum: 823576f4e0fc535fe06af2f3b7c89bc0 (MD5) Made available in DSpace on 2013-08-22T16:40:35Z (GMT). No. of bitstreams: 5 Ali_Vakilian.pdf: 614134 bytes, checksum: 823576f4e0fc535fe06af2f3b7c89bc0 (MD5) figures.zip: 124579 bytes, checksum: 37c7cb93fa408c51336e23a2948773a3 (MD5) ms_thesis.bib: 13403 bytes, checksum: d2f7f0fabda6c5947dc32c1dfad862c6 (MD5) nw-pc-sndp-thesis.tex: 166441 bytes, checksum: bf19e9e3ba79a53f273b70189ead566c (MD5) license.txt: 4062 bytes, checksum: 1061906d751569d27c834d2c94922242 (MD5) http://hdl.handle.net/2142/45452 en Copyright 2013 Ali Vakilian Approximation Algorithm Survivable Network Design Steiner Network Prize-collecting survivable network design problem (SNDP) Node-weighted prize-collecting survivable network design problems text Computer Science 1434 Computer Science 0112 University of Illinois at Urbana-Champaign Thesis M.S. MS:Computer Science -UIUC 10KS0112MS