<?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:40:51Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/2923" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/2923</identifier><datestamp>2017-03-21T19:53:41Z</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="326c9f07-0951-46a2-b7e9-47d062249050" confidence="600">Wu, Huayue</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2007-05-08T14:00:53Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2007-05-08T14:00:53Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2006</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2006</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/2923</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The runtime for solving constraint satisfaction problems (CSP) and propositional satisfiability problems (SAT) using systematic backtracking search has been shown to exhibit great variability.    Randomization and restarts is an effective technique for reducing such variability to achieve better expected performance.    Several restart strategies have been proposed and studied in previous work and show differing degrees of empirical effectiveness.    &amp;lt;br /&amp;gt;&amp;lt;br /&amp;gt;  The first topic in this thesis is the extension of analytical results on restart strategies through the introduction of physically based assumptions.    In particular, we study the performance of two of the restart strategies on Pareto runtime distributions.    We show that the geometric strategy provably removes heavy tail.    We also examine several factors that arise during implementation and their effects on existing restart strategies.    &amp;lt;br /&amp;gt;&amp;lt;br /&amp;gt;  The second topic concerns the development of a new hybrid restart strategy in a realistic problem setting.    Our work adapts the existing general approach on dynamic strategy but implements more sophisticated machine learning techniques.    The resulting hybrid strategy shows superior performance compared to existing static strategies and an improved robustness.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">455240 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: 2006, 
  Wu, Huayue. 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">CSP</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">SAT</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">restart strategy</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">backtrack search</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Randomization and Restart Strategies</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">School of Computer Science</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>