4 papers
If it is Good Then Drop it -- a Spiteful Poisson Process for Submodular Maximization
Ariel Kulik, Thiago Oliveira, Roy Schwartz +1
We study the problem of maximizing a general and not necessarily monotone submodular function subject to a matroid independence constraint. This problem has a rich history, with mu…
A Poisson Process for Submodular Maximization
Amit Ganz Rozenman, Ariel Kulik, Roy Schwartz +1
We study the problem of maximizing a monotone submodular function subject to a matroid independence constraint. For more than a decade, a rich body of work has studied this problem…
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
BarıŠCan Esmer, Ariel Kulik, Dániel Marx +2
We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J. ACM 2019], by establishing a connection between parameterized approximation and expon…
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Ariel Kulik, Hadas Shachnai
In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best k…