<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T16:56:55Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/7557" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/7557</identifier><datestamp>2019-04-03T02:43:31Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="8a3694b0-710c-4b4c-96c2-8b071edb5a34" confidence="600">Sadeghian Sadeghabad, Sina</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2013-05-23T14:45:32Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2013-05-23T14:45:32Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2013-05-23T14:45:32Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2013</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/7557</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The Steiner Tree problem has appeared in the Karp&amp;apos;s list of the first 21 NP-hard problems and is well known as one of the most fundamental problems in Network Design area. We study the Node-Weighted version of the Prize &#xd;
Collecting Steiner Tree problem.&#xd;
In this problem, we are given a simple graph with a cost and penalty value associated with each node. Our&#xd;
goal is to find a subtree T of the graph minimizing the cost of the &#xd;
nodes in T plus penalty of the nodes not in T. By a reduction&#xd;
from set cover problem it can be easily shown that the problem cannot be approximated in polynomial time within factor of (1-o(1))ln n unless NP has quasi-polynomial time algorithms, where n is the number of vertices of the graph. &#xd;
&#xd;
Moss and Rabani claimed an O(log n)-approximation algorithm for the problem using a Primal-Dual approach in their STOC&amp;apos;01 paper \cite{moss2001}.  We show that their algorithm is incorrect by providing a counter example in which there is an O(n) gap between the dual solution constructed by their algorithm and the optimal solution. Further, evidence is given that their algorithm probably does not have a simple fix. We propose a new algorithm which is more involved and&#xd;
introduces novel ideas in primal dual approach for network design problems. Also, our algorithm is a Lagrangian Multiplier Preserving algorithm and we show how  this property can be utilized to design an O(log n)-approximation algorithm for the Node-Weighted Quota Steiner Tree problem &#xd;
using the Lagrangian Relaxation method. &#xd;
&#xd;
We also show an application of the Node Weighted Quota Steiner Tree problem in designing algorithm with better approximation factor for &#xd;
Technology Diffusion problem, a problem proposed by Goldberg and Liu &#xd;
in \cite{goldberg2012} (SODA 2013). In Technology Diffusion, we are given a graph G and a threshold θ(v) associated with each vertex v and we are seeking a set of initial nodes called the seed set.&#xd;
Technology Diffusion is a dynamic process defined over time in which each vertex is either active or inactive. The vertices in the seed set &#xd;
are initially activated and each other vertex v gets activated whenever there are at least θ(v) active nodes connected to &#xd;
v through other active nodes. The Technology Diffusion problem asks to &#xd;
find the minimum seed set activating all nodes. Goldberg &#xd;
and Liu gave an O(rllog n)-approximation algorithm for the problem where&#xd;
r and l are the diameter of G and the number of distinct threshold values, respectively. We improve the approximation factor&#xd;
to O(min{r,l}log n) by establishing a close connection between the problem and the Node Weighted Quota Steiner Tree problem.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">node-weighted prize collecting Steiner tree</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">approximation algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">network design</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">node-weighted quota steiner tree</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">technology diffusion</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">primal dual algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Node-Weighted Prize Collecting Steiner Tree and Applications</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>