Publications

In this paper, we use dependent rounding to obtain randomized fair allocations of indivisible goods with strong ex-post and ex-ante fairness guarantees.

In this paper, we study the problem of  sorting in the comparison model under adversarial corruption of some subset of  the elements. Comparing a corrupt element with another (corrupt or otherwise) element can yield an arbitrary result, and the aim is to retrieve an ordering whose distance from the true ordering is not large in terms of the number of corrupt elements. We show interesting implications to the k-median problem under the Ulam metric.

In this paper, we study the capacitated Nash welfare problem, and present a constant factor algorithm for both the one-sided and the two-sided settings, under submodular and subadditive valuations respectively.

Here, we study the capacitated version of the sum of radii clustering problem where the objective is to minimize the sum of radii of the clusters. We give improved upper bounds on the FPT approximation ratios of both the uniformly and non-uniformly capacitated versions. We also prove approximation hardness under ETH.

Here we consider the sorting problem generalized to trees. Suppose you have a hidden rooted tree and you can make pairwise comparisons of nodes, where x>y if x is an ancestor of y. The task is to reconstruct the tree. We give an asymptotically optimal randomized algorithm in terms of the maximum degree.