Toby Walsh,

National ICT Australia and University of New South Wales

Abstract:

Whilst waiting for a search procedure like a TSP or SAT solver to finish, you might ask yourself a number of questions. Is the search procedure just about to come back with an answer, or has it taken a wrong turn? Should I go for coffee and expect to find the answer on my return? Is it worth leaving this to run overnight, or should I just quit as this search is unlikely ever to finish? To help answer such questions, we propose some new online methods for estimating the size of a backtracking search tree.

 

Date: 2006-Jun-29     Time: 10:30:00     Room: 336


For more information: