7 citations · 9 across the 12 of their papers we have counts for
8 papers · 1 filter
Approximate Monotone Local Search for Weighted Problems
Baris Can Esmer, Ariel Kulik, Daniel Marx +2
In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algor…
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…
Budgeted Matroid Maximization: a Parameterized Viewpoint
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an -matchoid $\cm$ on a ground set , a profit function $p:E \righta…
Improved Approximation for Two-dimensional Vector Multiple Knapsack
Tomer Cohen, Ariel Kulik, Hadas Shachnai
We study the uniform -dimensional vector multiple knapsack (2VMK) problem, a natural variant of multiple knapsack arising in real-world applications such as virtual machine plac…
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…
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
The goal of this paper is to understand how exponential-time approximation algorithms can be obtained from existing polynomial-time approximation algorithms, existing parameterized…