Quasiconvex analysis of backtracking algorithms

MaRDI QIDQ5501340zbMATH OpenFDO

Authors David Eppstein

Publication date 3 August 2015

Full work available at URL https://arxiv.org/abs/cs/0304018

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonconvex programming, global optimization (90C26)

Abstract: 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.

Recommendations

• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• A measure \& conquer approach for the analysis of exact algorithms
• Automata, Languages and Programming
• scientific article; zbMATH DE number 1113993
• Multidimensional Divide-and-Conquer Maximin Recurrences

Cited in

(8)

• Non-polynomial worst-case analysis of recursive programs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Exact Algorithms for Edge Domination
• scientific article; zbMATH DE number 67459 (Why is no real title available?)
• scientific article; zbMATH DE number 1086900 (Why is no real title available?)

Describes a project that uses

Uses Software

• xrc
• Python

This page was built for publication: Quasiconvex analysis of backtracking algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501340)