# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2206.13481.pdf

(Preprint), 391KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Esmer, B. C., Kulik, A., Marx, D., Neuen, D., & Sharma, R. (2022). Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. Retrieved from https://arxiv.org/abs/2206.13481.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1E6F-8

##### Abstract

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

monotone subset minimization problems. In a 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 approximate

monotone local search to show that a parameterized $\alpha$-approximation

algorithm that runs in $c^k \cdot n^{O(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^{O(1)}$ time, where $d$ is the unique value in $d \in

(1,1+\frac{c-1}{\alpha})$ such that

$\mathcal{D}(\frac{1}{\alpha}\|\frac{d-1}{c-1})=\frac{\ln c}{\alpha}$ and

$\mathcal{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 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

\cdot n^{O(1)}$, improving upon the previously best known $1.1$-approximation

running in time $1.127^n \cdot n^{O(1)}$ by Bourgeois et al. [DAM 2011].

Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between

parameterized approximation and exponential-time approximation algorithms for

monotone subset minimization problems. In a 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 approximate

monotone local search to show that a parameterized $\alpha$-approximation

algorithm that runs in $c^k \cdot n^{O(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^{O(1)}$ time, where $d$ is the unique value in $d \in

(1,1+\frac{c-1}{\alpha})$ such that

$\mathcal{D}(\frac{1}{\alpha}\|\frac{d-1}{c-1})=\frac{\ln c}{\alpha}$ and

$\mathcal{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 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

\cdot n^{O(1)}$, improving upon the previously best known $1.1$-approximation

running in time $1.127^n \cdot n^{O(1)}$ by Bourgeois et al. [DAM 2011].