4 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…
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 minimize…
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…