{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/45452"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/45452","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Node-weighted prize-collecting survivable network design problems","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.","abstract_html":"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 <span class=\"etd-inline-math\">&pi;(st)</span> 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 <span class=\"etd-inline-math\">k = \\max<sub>st</sub> r(st)</span> be the maximum requirement. There has been no non-trivial approximation for node-weighted PC-SNDP for $k &gt; 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 <span class=\"etd-inline-math\">O(k<sup>4</sup> \\log<sup>2</sup> n)</span>-approximation for PC-VC-SNDP which improves to <span class=\"etd-inline-math\">O(k<sup>4</sup> \\log n)</span> on instances from a minor-closed families of graphs.","abstract_has_math":true,"creators":["Vakilian, Ali"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chekuri, Chandra S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-08-22T16:40:35Z","date_published":"2013-08-22T16:40:35Z","updated_at":"2026-07-22T22:25:34Z","subjects":["Approximation Algorithm","Survivable Network Design","Steiner Network","Prize-collecting survivable network design problem (SNDP)"],"languages":["en"],"rights":["Copyright 2013 Ali Vakilian"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/45452","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chekuri, Chandra S."]},{"key":"dc:creator","label":"Author","values":["Vakilian, Ali"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-08-22T16:40:35Z","2013-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Approximation Algorithm","Survivable Network Design","Steiner Network","Prize-collecting survivable network design problem (SNDP)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Ali Vakilian"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/45452"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)"]},{"key":"dc:title","label":"Title","values":["Node-weighted prize-collecting survivable network design problems"]}]}],"canonical_facts":{"dc:contributor":["Chekuri, Chandra S."],"dc:creator":["Vakilian, Ali"],"dc:date":["2013-08-22T16:40:35Z","2013-08"],"dc:description":["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)"],"dc:identifier":["http://hdl.handle.net/2142/45452"],"dc:language":["en"],"dc:rights":["Copyright 2013 Ali Vakilian"],"dc:subject":["Approximation Algorithm","Survivable Network Design","Steiner Network","Prize-collecting survivable network design problem (SNDP)"],"dc:title":["Node-weighted prize-collecting survivable network design problems"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:34Z"}