6 papers · 1 filter
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…
An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
In [Math. Oper. Res., 2011], Fleischer et al. introduced a powerful technique for solving the generic class of separable assignment problems (SAP), in which a set of items of given…
Lower Bounds for Matroid Optimization Problems with a Linear Constraint
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements which optimizes (i.e., maximizes or minimizes) a…