5 citations · 10 across the 4 of their papers we have counts for
8 papers · 1 filter
Approximation Algorithms for Generalized Multidimensional Knapsack
Arindam Khan, Eklavya Sharma, K. V. N. Sreenivas
We study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and nonnegative…
Best Fit Bin Packing with Random Order Revisited
Susanne Albers, Arindam Khan, Leon Ladewig
Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a s…
Improved Online Algorithms for Knapsack and GAP in the Random Order Model
Susanne Albers, Arindam Khan, Leon Ladewig
The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum prof…
Group Fairness for Knapsack Problems
Deval Patel, Arindam Khan, Anand Louis
We study the knapsack problem with group fairness constraints. The input of the problem consists of a knapsack of bounded capacity and a set of items, each item belongs to a partic…
The Matching Augmentation Problem: A -Approximation Algorithm
Joe Cheriyan, Jack Dippel, Fabrizio Grandoni +2
We present a approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost ze…
Improved Pseudo-Polynomial-Time Approximation for Strip Packing
Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala +1
We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in…