<?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-22T17:43:06Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/6317" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/6317</identifier><datestamp>2017-03-21T17:41:59Z</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="c4334945-b338-45d4-ae1d-33b07942f940" confidence="600">Grant, Elyot</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2011-09-30T15:29:20Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2011-09-30T15:29:20Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2011-09-30T15:29:20Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2011</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/6317</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science.  Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP.  However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time.  Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible.&#xd;
&#xd;
In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems.  We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure.  In particular, we provide:&#xd;
&#xd;
- An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC.&#xd;
&#xd;
- A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure.&#xd;
&#xd;
- A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity.&#xd;
&#xd;
- Applications of the above to various capacitated covering problems via linear programming strengthening and rounding.&#xd;
&#xd;
In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure.  We tabulate these problems and classify them according to their approximability.</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">set cover</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">combinatorial optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">computational geometry</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">quasi-uniform sampling</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">hitting set</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">apx-hard</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">dynamic programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">capacitated covering</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">Covering Problems via Structural Approaches</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="comment" qualifier="hidden" lang="en">If possible, could the Abstract use an m-dash (in place of the --) and bullets (in place of the - marks)?</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>