2 papers
cs.DS2022
An EPTAS for Budgeted Matroid Independent Set
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We consider the budgeted matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a matroid over the elements…
cs.DS2020
An APTAS for Bin Packing with Clique-graph Conflicts
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study the following variant of the classic {\em bin packing} problem. Given a set of items of various sizes, partitioned into groups, find a packing of the items in a minimum nu…