research
∙
08/21/2023
Fair Rank Aggregation
Ranking algorithms find extensive usage in diverse areas such as web sea...
share
research
∙
05/02/2023
Guaranteeing Envy-Freeness under Generalized Assignment Constraints
We study fair division of goods under the broad class of generalized ass...
research
∙
03/16/2023
Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set
Set cover and hitting set are fundamental problems in combinatorial opti...
research
∙
08/19/2022
Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits
We study the Improving Multi-Armed Bandit (IMAB) problem, where the rewa...
research
∙
08/17/2022
Finding Fair Allocations under Budget Constraints
We study the fair allocation of indivisible goods among agents with iden...
research
∙
05/27/2022
Fairness and Welfare Quantification for Regret in Multi-Armed Bandits
We extend the notion of regret with a welfarist perspective. Focussing o...
research
∙
05/07/2022
Near-optimal Algorithms for Stochastic Online Bin Packing
We study the online bin packing problem under two stochastic settings. I...
research
∙
02/24/2022
A PTAS for Packing Hypercubes into a Knapsack
We study the d-dimensional hypercube knapsack problem where we are given...
research
∙
02/12/2022
Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing
In the Strip Packing problem (SP), we are given a vertical half-strip [0...
research
∙
02/07/2022
Approximation Algorithms for ROUND-UFP and ROUND-SAP
We study ROUND-UFP and ROUND-SAP, two generalizations of the classical B...
research
∙
11/09/2021
A PTAS for the horizontal rectangle stabbing problem
We study rectangle stabbing problems in which we are given n axis-aligne...
research
∙
09/02/2021
Universal and Tight Online Algorithms for Generalized-Mean Welfare
We study fair and efficient allocation of divisible goods, in an online ...
research
∙
06/26/2021
Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing
We study the generalized multidimensional bin packing problem (GVBP) tha...
research
∙
06/01/2021
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
We study the Maximum Independent Set of Rectangles (MISR) problem, where...
research
∙
05/15/2021
Peak Demand Minimization via Sliced Strip Packing
We study Nonpreemptive Peak Demand Minimization (NPDM) problem, where we...
research
∙
05/06/2021
Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items
In the Two-dimensional Bin Packing (2BP) problem, we are given a set of ...
research
∙
03/18/2021
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsa...
research
∙
03/17/2021
On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem
In two-dimensional geometric knapsack problem, we are given a set of n a...
research
∙
02/11/2021
Approximation Algorithms for Generalized Multidimensional Knapsack
We study a generalization of the knapsack problem with geometric and vec...
research
∙
12/09/2020
Streaming Algorithms for Stochastic Multi-armed Bandits
We study the Stochastic Multi-armed Bandit problem under bounded arm-mem...
research
∙
12/01/2020
Best Fit Bin Packing with Random Order Revisited
Best Fit is a well known online algorithm for the bin packing problem, w...
research
∙
12/01/2020
Improved Online Algorithms for Knapsack and GAP in the Random Order Model
The knapsack problem is one of the classical problems in combinatorial o...
research
∙
06/14/2020
Group Fairness for Knapsack Problems
We study the knapsack problem with group fairness constraints. The input...
research
∙
10/17/2018
The Matching Augmentation Problem: A 7/4-Approximation Algorithm
We present a 7/4 approximation algorithm for the matching augmentation p...
research
∙
01/23/2018
Improved Pseudo-Polynomial-Time Approximation for Strip Packing
We study the strip packing problem, a classical packing problem which ge...
research
∙
11/21/2017