Professor David Kirkpatrick from the University of British Columbia, Vancouver, will give a guest talk on Thursday 11 June at 10, in Exactum C222.
Title: Hyperbolic dovetailing
Abstract:
A familiar quandary, in many settings (computational and otherwise), arises when there are several possible alternatives for the solution of a problem, but no way of knowing which, if any, are viable for a particular problem instance. Faced with this uncertainty, we are forced to simulate the parallel exploration of alternatives through some kind of coordinated interleaving (dovetailing) process. The goal, as usual, is to find a solution with low total cost. Much of the existing work on such problems has assumed, implicitly or explicitly, that at most one of the alternatives is viable. This assumption provides support for a competitive analysis of algorithms (using the cost of the unique viable alternative as a benchmark).
However, just as it is unrealistic to analyse algorithms in terms of the worst case cost of the alternative solutions or their worst-case ordering (giving rise to competitive analysis), it is also unrealistic in many scenarios to make the worst-case assumption that at most one of the alternatives is viable. In this talk, we relax this assumption in revisiting several familiar dovetailing problems.
Our main contribution is the introduction of a novel process interleaving technique, called hyperbolic dovetailing that achieves a competitive ratio that is within a logarithmic factor of optimal on all inputs in the worst, average and expected cases, over all possible deterministic (and randomized) dovetailing schemes. We also show that no other dovetailing strategy can guarantee an asymptotically smaller competitive ratio for all inputs.
An interesting application of hyperbolic dovetailing arises in the design of what we call input-thrifty algorithms, algorithms that are designed to minimize the total precision of the input requested in order to evaluate some given predicate. We show that for some very basic predicates involving real numbers (such as certifying that the numbers are not all identical) we can use hyperbolic dovetailing to provide input-thrifty algorithms that are competitive, in this novel cost measure, with the best algorithms that solve these problems.
Last updated on 3 Jun 2009 by Visa Noronen - Page created on 11 Jun 2009 by Visa Noronen