4 papers · 1 filter
Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D
Karl Bringmann, Ariel Kulik, Karol Węgrzycki
We revisit the -dimensional Vector Knapsack problem (-Knapsack): Given a -dimensional capacity vector and a set of items, each with a -dimensional weight vector and a p…
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 -…
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…
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…