cispa_all_3846.pdf (928.63 kB)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search

Download (928.63 kB)
conference contribution
posted on 2023-11-29, 18:26 authored by Baris Can Esmer, Ariel Kulik, Dániel MarxDániel Marx, Daniel Neuen, Roohani Sharma
We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between parameterized approximation and exponential-time approximation algorithms for {\em monotone subset minimization} problems. In a {\em monotone subset minimization} problem the input implicitly describes a non-empty set family over a universe of size $n$ which is closed under taking supersets. The task is to find a minimum cardinality set in this family. Broadly speaking, we use {\em approximate monotone local search} to show that a parameterized $\alpha$-approximation algorithm that runs in $c^k \cdot n^{\OO(1)}$ time, where $k$ is the solution size, can be used to derive an $\alpha$-approximation randomized algorithm that runs in $d^n \cdot n^{\OO(1)}$ time, where $d$ is the unique value in $d\in \left (1, 1+\frac{c-1}{\alpha} \right)$ such that $\D{\frac{1}{\alpha}}{\frac{d-1}{c-1}} =\frac{\ln c }{\alpha}$ and $\D{a}{b}$ is the Kullback-Leibler divergence. This running time matches that of Fomin et al.\ for $\alpha=1$, and is strictly better when $\alpha >1$, for any $c >1$. Furthermore, we also show that this result can be derandomized at the expense of a sub-exponential multiplicative factor in the running time. We use an approximate variant of the exhaustive search as a benchmark for our algorithm. We show that the classic $2^n \cdot n^{\OO(1)}$ exhaustive search can be adapted to an $\alpha$-approximate exhaustive search that runs in time $\left ( 1+ \exp\left (-\alpha \cdot \entropy\left (\frac{1}{\alpha}\right)\right)\right)^n \cdot n^{\OO(1)}$, where $\entropy$ 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 {\sc Vertex Cover}, {\sc $3$-Hitting Set}, {\sc Directed Feedback Vertex Set}, {\sc Directed Subset Feedback Vertex Set}, {\sc Directed Odd Cycle Transversal} and {\sc Undirected Multicut}. For instance, we get a $1.1$-approximation algorithm for {\sc Vertex Cover} with running time $1.114^n \cdot n^{\OO(1)}$, improving upon the previously best known $1.1$-approximation running in time $1.127^n \cdot n^{\OO(1)}$ by Bourgeois et al.\ [DAM 2011].


Preferred Citation

Esmer Can, Ariel Kulik, Dániel Marx, Daniel Neuen and Roohani Sharma. Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. In: European Symposium on Algorithms (ESA). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

European Symposium on Algorithms (ESA)

Legacy Posted Date


Open Access Type

  • Green


@inproceedings{cispa_all_3846, title = "Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search", author = "Can Esmer, Baris and Kulik, Ariel and Marx, Dániel and Neuen, Daniel and Sharma, Roohani", booktitle="{European Symposium on Algorithms (ESA)}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager