2 papers
cs.DS2023
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…
cs.DS2023
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.…