<?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-22T15:48:50Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1075" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1075</identifier><datestamp>2017-03-21T19:05:43Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</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" lang="en" authority="160103cd-940e-41d9-b8f7-4778294df9c3" confidence="600">Southey, Finnegan</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:29:25Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:29:25Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1075</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">This dissertation explores approaches to the satisfiability problem, focusing on local search methods.   The research endeavours to better understand how and why some local search methods are effective.   At the root of this understanding are a set of metrics that characterize the behaviour of local search methods.   Based on this understanding, two new local search methods are proposed and tested, the first, SDF, demonstrating the value of the insights drawn from the metrics, and the second, ESG, achieving state-of-the-art performance and generalizing the approach to arbitrary 0-1 integer linear programming problems.   This generality is demonstrated by applying ESG to combinatorial auction winner determination.   Further augmentations to local search are proposed and examined, exploring hybrids that incorporate aspects of backtrack search methods.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">995042 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</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="rights" lang="en">Copyright: 2004, 
  Southey, Finnegan. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">artificial intelligence</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">satisfiability</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">constraint satisfaction</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">constrained optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">local search</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Augmenting Local Search for Satisfiability</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral 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">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</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>