Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search


Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 391KB

Supplementary Material (public)
There is no public supplementary material available

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
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].