5 papers
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…
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…
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.…