Hyperbolic dovetailing

David Kirkpatrick

A familiar quandary 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 un- certainty, one is forced to simulate the parallel exploration of alternatives through some kind of co-ordinated interleaving (dovetailing) process. As usual, the goal is to Ūnd a solution with low total cost. Much of the exist- ing work on such problems has assumed, implicitly or explicitly, that at most one of the alternatives is viable, providing support for a competi- tive analysis of algorithms (using the cost of the unique viable alternative as a benchmark). In this paper, we relax this worst-case assumption in revisiting several familiar dovetailing problems. Our main contribution is the introduction of a novel process interleav- ing 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 in- volving real numbers 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.