Quasiconvex Analysis of Backtracking Algorithms
| dc.creator | Eppstein, David | |
| dc.date | 2003-04-10 | |
| dc.date | 2003-07-09 | |
| dc.date.accessioned | 2026-07-07T03:19:35Z | |
| dc.date.available | 2026-07-07T03:19:35Z | |
| dc.description | 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. | |
| dc.description | 12 pages, 2 figures. This revision includes a larger example recurrence and reports on a second implementation of the algorithm | |
| dc.identifier | https://arxiv.org/abs/cs/0304018 | |
| dc.identifier | http://arxiv.org/abs/cs/0304018 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31523 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Geometry | |
| dc.subject | Combinatorics | |
| dc.subject | F.2.2; G.1.6 | |
| dc.title | Quasiconvex Analysis of Backtracking Algorithms | |
| dc.type | text |