Campus Event Calendar

Event Entry

What and Who

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search

Ariel Kulik
CISPA Helmholtz Center for Information Security
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 30 May 2023
30 Minutes
E1 4


In this paper, 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 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 n^{O(1)}
time, where d is the unique value in (1, 1+ ((c-1)/\alpha)) such that
D(1 / \alpha || (d-1)/(c-1)) = 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 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].


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 05/26/2023 13:40
Roohani Sharma, 05/08/2023 17:30 -- Created document.