Quasiconvex Analysis of Backtracking Algorithms
<|reference_start|>Quasiconvex Analysis of Backtracking Algorithms: 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.<|reference_end|>
@article{eppstein2003quasiconvex,
    title={Quasiconvex Analysis of Backtracking Algorithms},
    author={David Eppstein},
    journal={arXiv preprint arXiv:cs/0304018},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0304018},
    primaryClass={cs.DS cs.CG math.CO}
}