Accelerating Random Walks

In recent years, there has been much research on local search techniques for solving constraint satisfaction problems, including Boolean satisfiability problems. Some of the most successful procedures combine a form of random walk with a greedy bias. These procedures are quite e#ective in a number of problem domains, for example, constraint-based planning and scheduling, graph coloring, and hard random problem instances. However, i