7 citations · 9 across the 12 of their papers we have counts for
5 papers · 1 filter
Bin Packing with Partition Matroid can be Approximated within Bins
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in , and a partition matroid over the items. The goal is to pac…
An EPTAS for Budgeted Matroid Independent Set
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We consider the budgeted matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a matroid over the elements…
Computing Generalized Convolutions Faster Than Brute Force
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
In this paper, we consider a general notion of convolution. Let be a finite domain and let be the set of -length vectors (tuples) of . Let be…
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J. ACM 2019], by establishing a connection between parameterized approximation and expon…
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding
Ariel Kulik, Matthias Mnich, Hadas Shachnai
We study the -dimensional Vector Bin Packing (VBP) problem, a generalization of Bin Packing with central applications in resource allocation and scheduling. In VBP, we are…