Explanipedia

Near-optimal Algorithms for Stochastic Online Bin Packing Open

Nikhil Ayyadevara, Rajni Dabas, Arindam Khan, Kidambi Sreenivas · 2025

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 minimum number of unit-sized bins. First, we study bin pa…

Improved Approximation Algorithms for Three-Dimensional Bin Packing Open

Debajyoti Kar, Arindam Khan, Malin Rau · 2025

We study three fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), 3D Strip Packing (3D-SP), and Minimum Volume Bounding Box (3D-MVBB), where given a set of 3D (rectangular) cuboids, the goal …

An Improved Guillotine Cut for Squares Open

Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, Andreas Wiese · 2025

Given a set of n non-overlapping geometric objects, can we separate a constant fraction of them using straight-line cuts that extend from edge to edge? In 1996, Urrutia posed this question for compact convex objects. Pach and Tardos later …

Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects Open

Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal , et al. · 2024

We study the geometric knapsack problem in which we are given a set of d-dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that can be packed non-overlappingly into a given d-dimensional (…

Random-Order Online Independent Set of Intervals and Hyperrectangles Open

Mohit Garg, Debajyoti Kar, Arindam Khan · 2024

In the Maximum Independent Set of Hyperrectangles problem, we are given a set of n (possibly overlapping) d-dimensional axis-aligned hyperrectangles, and the goal is to find a subset of non-overlapping hyperrectangles of maximum cardinalit…

On Approximation Schemes for Stabbing Rectilinear Polygons Open

Arindam Khan, Aditya Subramanian, Tobias Widmann, Andreas Wiese · 2024

We study the problem of stabbing rectilinear polygons, where we are given n rectilinear polygons in the plane that we want to stab, i.e., we want to select horizontal line segments such that for each given rectilinear polygon there is a li…

Bin Packing under Random-Order: Breaking the Barrier of 3/2 Open

Anish Arvind Hebbar, Arindam Khan, Kidambi Sreenivas · 2024

Best-Fit is one of the most prominent and practically used algorithms for the\nbin packing problem, where a set of items with associated sizes needs to be\npacked in the minimum number of unit-capacity bins. Kenyon [SODA '96] studied\nonli…

Fair Rank Aggregation Open

Diptarka Chakraborty, Syamantak Das, Arindam Khan, Aditya Subramanian · 2023

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 multiple rankings into a single aggregate ranking. However, …

Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits Open

Vishakha Patil, Vineet Nair, Ganesh Ghalme, Arindam Khan · 2023

We study the Improving Multi-Armed Bandit problem, where the reward obtained from an arm increases with the number of pulls it receives. This model provides an elegant abstraction for many real-world problems in domains such as education a…

Peak Demand Minimization via Sliced Strip Packing Open

Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, Malte Tutas · 2023

We study the Non-preemptive 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 schedule all jobs within a fixed time period such that the p…

Fairness and Welfare Quantification for Regret in Multi-Armed Bandits Open

Siddharth Barman, Arindam Khan, Arnab Maiti, Ayush Sawarni · 2023

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 algorithms by applying a fundamental welfare function, namely t…

Finding Fair Allocations under Budget Constraints Open

Siddharth Barman, Arindam Khan, Sudarshan Shyam, Kidambi Sreenivas · 2023

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 specific size and value--need to be allocated such that the bund…

A Tight $$(3/2+\varepsilon )$$-Approximation for Skewed Strip Packing Open

Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan , et al. · 2023

In the Strip Packing problem, we are given a vertical half-strip [0 , W] × [0 , + ∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip su…

Guaranteeing Envy-Freeness under Generalized Assignment Constraints Open

Siddharth Barman, Arindam Khan, Sudarshan Shyam, Kidambi Sreenivas · 2023

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 one needs to allocate the goods among the agents fairly wh…

Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set Open

Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, Andreas Wiese · 2023

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 versions of these problems and present new online and dynamic algo…

Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines Open

Arindam Khan, Eklavya Sharma, Kidambi Sreenivas · 2023

We study the classic weighted maximum throughput problem on unrelated machines. We give a (1-1/e-ε)-approximation algorithm for the preemptive case. To our knowledge this is the first ever approximation result for this problem. It is an im…

Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits Open

Vishakha Patil, Vineet Nair, Ganesh Ghalme, Arindam Khan · 2022

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 abstraction for many real-world problems in domains such as educ…

Finding Fair Allocations under Budget Constraints Open

Siddharth Barman, Arindam Khan, Sudarshan Shyam, Kidambi Sreenivas · 2022

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 specific size and value--need to be allocated such that the bund…

Universal and Tight Online Algorithms for Generalized-Mean Welfare Open

Siddharth Barman, Arindam Khan, Arnab Maiti · 2022

We study fair and efficient allocation of divisible goods, in an online manner, among n agents. The goods arrive online in a sequence of T time periods. The agents' values for a good are revealed only after its arrival, and the online algo…

Fairness and Welfare Quantification for Regret in Multi-Armed Bandits Open

Siddharth Barman, Arindam Khan, Arnab Maiti, Ayush Sawarni · 2022

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 algorithms by applying a fundamental welfare function, namely t…

Near-optimal Algorithms for Stochastic Online Bin Packing Open

Nikhil Ayyadevara, Rajni Dabas, Arindam Khan, Kidambi Sreenivas · 2022

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 minimum number of unit-sized bins. First, we study bin packin…

A PTAS for Packing Hypercubes into a Knapsack Open

Klaus Jansen, Arindam Khan, Marvin Lira, Kidambi Sreenivas · 2022

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 hypercube. The goal is to find an axis-aligned non-overlapping…

Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing Open

Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, Andreas Wiese · 2022

In the Strip Packing problem (SP), we are given a vertical half-strip $[0,W]\times[0,\infty)$ and a set of $n$ axis-aligned rectangles of width at most $W$. The goal is to find a non-overlapping packing of all rectangles into the strip suc…

Approximation Algorithms for ROUND-UFP and ROUND-SAP Open

Debajyoti Kar, Arindam Khan, Andreas Wiese · 2022

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 allocation problem (SAP), respectively. We are given a path with ca…

A PTAS for the horizontal rectangle stabbing problem Open

Arindam Khan, Aditya Subramanian, Andreas Wiese · 2021

We study rectangle stabbing problems in which we are given $n$ axis-aligned rectangles in the plane that we want to stab, i.e., we want to select line segments such that for each given rectangle there is a line segment that intersects two …

Approximating Geometric Knapsack via L-packings Open

Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan , et al. · 2021

We study the two-dimensional geometric knapsack problem, in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) pack…

Universal and Tight Online Algorithms for Generalized-Mean Welfare Open

Siddharth Barman, Arindam Khan, Arnab Maiti · 2021

We study fair and efficient allocation of divisible goods, in an online manner, among $n$ agents. The goods arrive online in a sequence of $T$ time periods. The agents' values for a good are revealed only after its arrival, and the online …

Best Fit Bin Packing with Random Order Revisited Open

Susanne Albers, Arindam Khan, Leon Ladewig · 2021

Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing Open

Arindam Khan, Eklavya Sharma, Kidambi Sreenivas · 2021

We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given $n$ rectangular items where the $i^{\textrm{th}}$ item has width $w(i)$, height $h(i)$, and…

On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem Open

Arindam Khan, Arnab Maiti, Amatya Sharma, Andreas Wiese · 2021

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, integral height and an associated integral profit. The goal is …

Arindam Khan YOU? Author Swipe