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.