Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search

We use an approximate variant of the exhaustive search as a benchmark for our algorithm. We show that the classic 2^n n^{O(1)} exhaustive search can be adapted to an \alpha-approximate exhaustive search that runs in time (1+ exp(-\alpha H (1 / \alpha)))^n n^{O(1)}, where H is the entropy function. Furthermore, we provide a lower bound stating that the running time of this \alpha-approximate exhaustive search is the best achievable running time in an oracle model. When compared to approximate exhaustive search, and to other techniques, the running times obtained by approximate monotone local search are strictly better for any \alpha \geq 1, c >1.

We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for Vertex Cover, 3-Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we get a 1.1-approximation algorithm for Vertex Cover with running time 1.114^n n^{O(1)}, improving upon the previously best known 1.1-approximation running in time 1.127^n n^{O(1)} by Bourgeois et al. [DAM 2011].