7 citations · 12 across the 22 of their papers we have counts for
30 papers · 1 filter
Tight Approximation Results for Matroid Optimization with a Linear Constraint
Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions , and a threshold…
You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
The -matroid intersection (-MI) problem asks if given matroids share a common basis. Already for , notable canonical NP-complete special cases are -…
Approximations and Hardness of Packing Partially Ordered Items
Ilan Doron-Arad, Guy Kortsarz, Joseph Naor +2
Motivated by applications in production planning and storage allocation in hierarchical databases, we initiate the study of covering partially ordered items (CPO). Given a capacity…
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…