The Scaling of Search Cost

Abstract

We show that a rescaled constrainedness parameter provides the basis for accurate numerical models of search cost for both backtracking and local search algorithms. In the past, the scaling of performance has been restricted to critically constrained problems at the phase transition. Here, we show how to extend models of search cost to the full width of the phase transition. This enables the direct comparison of algorithms on both under-constrained and overconstrained problems. We illustrate the generality of the approach using three different problem domains (satisfiability, constraint satisfaction and travelling salesperson problems) with both backtracking algorithms like the Davis-Putnam procedure and local search algorithms like Gsat. As well as modelling data from experiments, we give accurate predictions for results beyond the range of the experiments. Introduction How does the performance of an algorithm scale? Theoretical analysis, especially average-case, can be very difficu...