31 citations · 53 across the 6 of their papers we have counts for
10 papers
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…
Streaming Algorithms for Stochastic Multi-armed Bandits
Arnab Maiti, Vishakha Patil, Arindam Khan
We study the Stochastic Multi-armed Bandit problem under bounded arm-memory. In this setting, the arms arrive in a stream, and the number of arms that can be stored in the memory a…
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…