Publications

In this work, we give FPT approximation schemes for sum-of-radii and sum-of-diameters clustring problems. Given a set of points in a metric space and a parameter k, the goal in sum-of-radii clustering is to find a partition into k clusters that minimizes the sum of radii of the clusters. In the sum-of-diameters clustering problem, the objective is to minimize the sum of diameters instead.

The sum-of-radii clustering problem is known to admit a QPTAS (quasi-polynomial time approximation scheme) and the existence of a PTAS is a major open problem. The best known approximation factor in polynomial time is 3 + ε and prior to our work, the best known FPT approximation factor was 2 + ε. We provide an FPT approximation scheme for this problem, achieving a (1+ε)-approximation. Since the problem is W[2]-hard, an exact FPT algorithm is unlikely. Thus, a  (1+ε)-approximation is essentially the strongest kind of positive FPT result one can hope for.

For the sum-of-diameters clustering problem, the best known FPT approximation factor prior to our work was 4 + ε. We provide a simple FPT approximation scheme here as well, and our algorithm extends to clustering with mergeable constraints.

In this work, we study the problem of finding a minimum weight subset of some given points that hit a given set of axis-parallel segments in the plane. The unweighted one-dimensional version of this problem is a standard early example in greedy algorithms, while its weighted one-dimensional analogue is also well known and can be solved exactly via dynamic programming. However, in 2D, this problem is known to be APX-hard for axis-parallel segments, while a trivial 2-approximation can be achieved by solving the two dimensions independently and taking their union. 

We provide a (1+2/e) approximation for the weighted case and 1 + 1/(e-1) for the unweighted case. Furthermore, in the case where all vertical segments are lines, we give a 1+1e approximation (for the weighted case), improving upon the previous known factor of 5/3 for the unweighted case. We also prove that the problem remains APX-hard even under this restriction.

This work studies the existence of almost equitable allocations under general valuation functions. In a fair division setting, consisting of a set of agents, a set of items, and agents’ valuations over subsets of items, the objective is to allocate the items so that all agents receive (nearly) equal value. We establish several structural and existence results for equitable allocations, and most notably resolve an open problem on the existence of EQ1 (equitable up to one item) allocations for non-negative valuations, by proving that such allocations always exist.

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.