1 citations · 1 across the 16 of their papers we have counts for
7 papers · 1 filter
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…
Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs
Ilan Doron-Arad, Hadas Shachnai
We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph , a weight function , a cost f…
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…
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…
An FPTAS for Budgeted Laminar Matroid Independent Set
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study the budgeted laminar matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a laminar matroid over…
Approximating Bin Packing with Conflict Graphs via Maximization Techniques
Ilan Doron-Arad, Hadas Shachnai
We give a comprehensive study of bin packing with conflicts (BPC). The input is a set of items, sizes , and a conflict graph . The goal is to…
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al.…