2 citations · 7 across the 14 of their papers we have counts for
23 papers
Online Geometric Packing through Online TSP Scheduling
Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae +3
We consider the problem of online packing of convex polygons into a strip by translations. While online algorithms with a constant competitive ratio have been known for rectangles…
Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
Kailash Gopal Darmasubramanian, Akash Pareek, Arindam Khan +1
Optimizing the timing and frequency of ads is a central problem in digital advertising, with significant economic consequences. Existing scheduling policies rely on simple heuristi…
Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
Pritam Acharya, Sujoy Bhore, Aaryan Gupta +3
We study the geometric knapsack problem in which we are given a set of -dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that…
On Approximation Schemes for Stabbing Rectilinear Polygons
Arindam Khan, Aditya Subramanian, Tobias Widmann +1
We study the problem of stabbing rectilinear polygons, where we are given rectilinear polygons in the plane that we want to stab, i.e., we want to select horizontal line segmen…
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…
Fair Rank Aggregation
Diptarka Chakraborty, Syamantak Das, Arindam Khan +1
Ranking algorithms find extensive usage in diverse areas such as web search, employment, college admission, voting, etc. The related rank aggregation problem deals with combining m…
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…
Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set
Arindam Khan, Aditya Lonkar, Saladi Rahul +2
Set cover and hitting set are fundamental problems in combinatorial optimization which are well-studied in the offline, online, and dynamic settings. We study the geometric version…
Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits
Vishakha Patil, Vineet Nair, Ganesh Ghalme +1
We study the Improving Multi-Armed Bandit (IMAB) problem, where the reward obtained from an arm increases with the number of pulls it receives. This model provides an elegant abstr…
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…
Fairness and Welfare Quantification for Regret in Multi-Armed Bandits
Siddharth Barman, Arindam Khan, Arnab Maiti +1
We extend the notion of regret with a welfarist perspective. Focussing on the classic multi-armed bandit (MAB) framework, the current work quantifies the performance of bandit algo…
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…
Approximation Algorithms for ROUND-UFP and ROUND-SAP
Debajyoti Kar, Arindam Khan, Andreas Wiese
We study ROUND-UFP and ROUND-SAP, two generalizations of the classical BIN PACKING problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocati…
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…
Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing
Arindam Khan, Aditya Lonkar, Arnab Maiti +2
In the Strip Packing problem (SP), we are given a vertical half-strip and a set of axis-aligned rectangles of width at most . The goal is to find a n…
A PTAS for the horizontal rectangle stabbing problem
Arindam Khan, Aditya Subramanian, Andreas Wiese
We study rectangle stabbing problems in which we are given axis-aligned rectangles in the plane that we want to stab, i.e., we want to select line segments such that for each g…
Universal and Tight Online Algorithms for Generalized-Mean Welfare
Siddharth Barman, Arindam Khan, Arnab Maiti
We study fair and efficient allocation of divisible goods, in an online manner, among agents. The goods arrive online in a sequence of time periods. The agents' values for…
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…
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
Waldo Gálvez, Arindam Khan, Mathieu Mari +3
We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overl…
Peak Demand Minimization via Sliced Strip Packing
Max A. Deppert, Klaus Jansen, Arindam Khan +2
We study Nonpreemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedu…
Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items
Arindam Khan, Eklavya Sharma
In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of…
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
Waldo Gálvez, Fabrizio Grandoni, Arindam Khan +2
In the \textsc{2-Dimensional Knapsack} problem (2DK) we are given a square knapsack and a collection of rectangular items with integer sizes and profits. Our goal is to find th…
On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem
Arindam Khan, Arnab Maiti, Amatya Sharma +1
In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, inte…