Quasiconvex analysis of backtracking algorithms.
D. Eppstein.
arXiv:cs.DS/0304018.
15th ACM-SIAM Symp. Discrete Algorithms,
New Orleans, 2004, pp. 781–790.
ACM Trans. Algorithms 2 (4): 492–509 (special issue for SODA 2004), 2006.
We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.
The journal version uses the longer title "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms".