Quasiconvex Analysis of Backtracking Algorithms

Details Quasiconvex Analysis of Backtracking Algorithms Quasiconvex Analysis of Backtracking Algorithms

2003-04-10

arxiv.org/abs/cs/0304018v2

Computer Science

Data Structures and Algorithms

12 pages, 2 figures. This revision includes a larger example recurrence and reports on a second implementation of the algorith

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Quasiconvex Analysis of Backtracking Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quasiconvex Analysis of Backtracking Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasiconvex Analysis of Backtracking Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-411218