4 citations · 8 across the 11 of their papers we have counts for
17 papers
Non-Linear Pricing Restores Tractability for a Data Seller
Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma +1
We consider a data seller who designs pricing mechanisms over multiple datasets to maximize revenue from budget-constrained buyers. The seller offers multiple datasets and assigns…
Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna
Jugal Garg, Eklavya Sharma, Xiaowei Wu
We study the problem of fairly allocating m indivisible items among n agents with possibly unequal entitlements in the mixed manna setting, where each item may be perceived as a go…
Equilibrium Pricing in Oligopolistic Data Markets
Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma +1
We study equilibrium pricing in oligopolistic data markets with budget-constrained buyers (e.g., machine learning companies purchasing data to improve model accuracy) and strategic…
Revenue-Optimal Pricing for Budget-Constrained Buyers in Data Markets
Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma +1
We study revenue-optimal pricing in data markets with rational, budget-constrained buyers. Such a market offers multiple datasets for sale, and buyers aim to improve the accuracy o…
Proportional and Pareto-Optimal Allocation of Chores with Subsidy
Jugal Garg, Eklavya Sharma, Xiaowei Wu
We consider the problem of allocating indivisible chores among agents with possibly different weights, aiming for a solution that is both fair and efficient. Specifically,…
Automating the Search for Small Hard Examples to Approximation Algorithms
Eklavya Sharma
Given an approximation algorithm , we want to find the input with the worst approximation ratio, i.e., the input for which 's output's objective value is the worst possible c…
Exploring Relations among Fairness Notions in Discrete Fair Division
Jugal Garg, Eklavya Sharma
Fair allocation of indivisible items among agents is a fundamental and extensively studied problem. However, fairness does not have a single universally accepted definition, leadin…
EF1 for Mixed Manna with Unequal Entitlements
Jugal Garg, Eklavya Sharma
We study fair division of indivisible mixed manna when agents have unequal entitlements, with weighted envy-freeness up to one item (WEF1) as our primary notion of fairness. We ide…
Best-of-Both-Worlds Fairness of the Envy-Cycle-Elimination Algorithm
Jugal Garg, Eklavya Sharma
We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and -MMS allocation can be obtained using…
Simplification and Improvement of MMS Approximation
Hannaneh Akrami, Jugal Garg, Eklavya Sharma +1
We consider the problem of fairly allocating a set of indivisible goods among agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since M…
New Fairness Concepts for Allocating Indivisible Items
Ioannis Caragiannis, Jugal Garg, Nidhi Rathi +2
For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelli…
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…
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…
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…
Analysis of the Harmonic Function Used in Bin-Packing
Eklavya Sharma
The harmonic function was first introduced by Lee and Lee (JACM 1985) for analyzing their online bin-packing algorithm. Subsequently, it has been used to obtain approximation algor…
An Approximation Algorithm for Covering Linear Programs and its Application to Bin-Packing
Eklavya Sharma
We give an -approximation algorithm for solving covering LPs, assuming the presence of a -approximation algorithm for a certain optimization problem. Our algorithm i…
Harmonic Algorithms for Packing d-dimensional Cuboids Into Bins
Eklavya Sharma
We explore approximation algorithms for the -dimensional geometric bin packing problem (BP). Caprara (MOR 2008) gave a harmonic-based algorithm for BP having an asymptotic…