1 citations · 2 across the 7 of their papers we have counts for
7 papers
Approximation Preserving Coresets
Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam
Clustering in a big data setting is an intensively studied problem, with coresets emerging as one of the important paradigms in this line of work. Given a cost function $\text{cost…
Existence and Computation of Fair Allocations under Constraints
Siddharth Barman, Ioannis Caragiannis, Sudarshan Shyam
We study fair division of divisible goods under generalized assignment constraints. Here, each good has an agent-specific value and size, and every agent has a budget constraint th…
A new lower bound for multi-color discrepancy with applications to fair division
Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam
A classical problem in combinatorics seeks colorings of low discrepancy. More concretely, the goal is to color the elements of a set system so that the number of appearances of any…
Simple and Optimal Sublinear Algorithms for Mean Estimation
Beatrice Bertolotti, Matteo Russo, Chris Schwiegelshohn +1
We study the sublinear multivariate mean estimation problem in -dimensional Euclidean space. Specifically, we aim to find the mean of a ground point set , which minimizes…
Low-Distortion Clustering with Ordinal and Limited Cardinal Information
Jakob Burkhardt, Ioannis Caragiannis, Karl Fehrs +3
Motivated by recent work in computational social choice, we extend the metric distortion framework to clustering problems. Given a set of agents located in an underlying metric…
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…