3 papers
cs.DS2025
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 -…
cs.DS2024
Fine Grained Lower Bounds for Multidimensional Knapsack
Ilan Doron-Arad, Ariel Kulik, Pasin Manurangsi
We study the -dimensional knapsack problem. We are given a set of items, each with a -dimensional cost vector and a profit, along with a -dimensional budget vector. The go…
cs.DS2024
Unsplittable Flow on a Short Path
Ilan Doron-Arad, Fabrizio Grandoni, Ariel Kulik
In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a su…