Show simple item record

dc.contributor.authorWu, Huayueen 14:00:53 (GMT) 14:00:53 (GMT)
dc.description.abstractThe 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. <br /><br /> 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. <br /><br /> 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.en
dc.format.extent455240 bytes
dc.publisherUniversity of Waterlooen
dc.rightsCopyright: 2006, Wu, Huayue. All rights reserved.en
dc.subjectComputer Scienceen
dc.subjectrestart strategyen
dc.subjectbacktrack searchen
dc.titleRandomization and Restart Strategiesen
dc.typeMaster Thesisen
dc.pendingfalseen of Computer Scienceen
uws-etd.degreeMaster of Mathematicsen

Files in this item


This item appears in the following Collection(s)

Show simple item record


University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages