4 citations · 8 across the 5 of their papers we have counts for
8 papers
Improved Approximation Algorithms for Three-Dimensional Knapsack
Klaus Jansen, Debajyoti Kar, Arindam Khan +2
We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective…
Bin Packing under Random-Order: Breaking the Barrier of 3/2
Anish Hebbar, Arindam Khan, K. V. N. Sreenivas
Best-Fit is one of the most prominent and practically used algorithms for the bin packing problem, where a set of items with associated sizes needs to be packed in the minimum numb…
Guaranteeing Envy-Freeness under Generalized Assignment Constraints
Siddharth Barman, Arindam Khan, Sudarshan Shyam +1
We study fair division of goods under the broad class of generalized assignment constraints. In this constraint framework, the sizes and values of the goods are agent-specific, and…
Finding Fair Allocations under Budget Constraints
Siddharth Barman, Arindam Khan, Sudarshan Shyam +1
We study the fair allocation of indivisible goods among agents with identical, additive valuations but individual budget constraints. Here, the indivisible goods--each with a speci…
Near-optimal Algorithms for Stochastic Online Bin Packing
Nikhil Ayyadevara, Rajni Dabas, Arindam Khan +1
We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in (0,1] and the goal is to pack them into the mi…
A PTAS for Packing Hypercubes into a Knapsack
Klaus Jansen, Arindam Khan, Marvin Lira +1
We study the d-dimensional hypercube knapsack problem where we are given a set of d-dimensional hypercubes with associated profits, and a knapsack which is a unit d-dimensional hyp…
Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing
Arindam Khan, Eklavya Sharma, K. V. N. Sreenivas
We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given rectangular items where the…
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…