Ariel Kulik

collaborators

2 papers

cs.DS2026

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 $d$ -dimensional Vector Knapsack problem ( $d$ -Knapsack): Given a $d$ -dimensional capacity vector and a set of items, each with a $d$ -dimensional weight vector and a p…

cs.DS2024

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 $ℓ = 3$ , notable canonical NP-complete special cases are $3$ -…