Esmer, Barış Can ;
Kulik, Ariel ;
Marx, Dániel ;
Neuen, Daniel ;
Sharma, Roohani
Faster ExponentialTime Approximation Algorithms Using Approximate Monotone Local Search
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 exponentialtime approximation algorithms for monotone subset minimization problems. In a monotone subset minimization problem the input implicitly describes a nonempty 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 αapproximation algorithm that runs in c^k⋅n^𝒪(1) time, where k is the solution size, can be used to derive an αapproximation randomized algorithm that runs in dⁿ⋅n^𝒪(1) time, where d is the unique value in (1, 1+{c1}/α) such that 𝒟(1/α‖{d1}/{c1}) = {ln c}/α and 𝒟(a‖b) is the KullbackLeibler divergence. This running time matches that of Fomin et al. for α = 1, and is strictly better when α > 1, for any c > 1. Furthermore, we also show that this result can be derandomized at the expense of a subexponential 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^𝒪(1) exhaustive search can be adapted to an αapproximate exhaustive search that runs in time (1+exp(α⋅ℋ(1/(α))))ⁿ⋅n^𝒪(1), where ℋ is the entropy function. Furthermore, we provide a lower bound stating that the running time of this α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 α ≥ 1, c > 1.
We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for Vertex Cover, 3Hitting Set, Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. For instance, we get a 1.1approximation algorithm for Vertex Cover with running time 1.114ⁿ⋅n^𝒪(1), improving upon the previously best known 1.1approximation running in time 1.127ⁿ⋅n^𝒪(1) by Bourgeois et al. [DAM 2011].
BibTeX  Entry
@InProceedings{esmer_et_al:LIPIcs.ESA.2022.50,
author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani},
title = {{Faster ExponentialTime Approximation Algorithms Using Approximate Monotone Local Search}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {50:150:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16988},
URN = {urn:nbn:de:0030drops169887},
doi = {10.4230/LIPIcs.ESA.2022.50},
annote = {Keywords: parameterized approximations, exponential approximations, monotone local search}
}
01.09.2022
Keywords: 

parameterized approximations, exponential approximations, monotone local search 
Seminar: 

30th Annual European Symposium on Algorithms (ESA 2022)

Issue date: 

2022 
Date of publication: 

01.09.2022 