2003/04/10 by David Eppstein, Eppstein, David
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #cs.CG #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.cs/0304018
12 pages, 2 figures. This revision includes a larger example recurrence and reports on a second implementation of the algorithm
arxiv created 2003/07/09 · arxiv updated 2009/11/30
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.