9 papers
Finding Representative and Approximately Efficient Committees
Dominik Peters, Rohit Vaish, Jatin Yadav
In approval-based committee voting, proportional approval voting (PAV) is a well-studied rule that combines proportional representation with Pareto efficiency. However, computing a…
Easier, but Not Easy: Nash Welfare under Lexicographic Valuations
Soumil Aggarwal, Rohit Vaish, Jatin Yadav
Maximizing Nash welfare over indivisible goods is a central problem in resource allocation. For additive valuations, the best-known approximation factor is roughly $e^{-1/e}\approx…
Hitting Axis-Parallel Segments with Weighted Points
Rajiv Raman, Siddhartha Sarkar, Jatin Yadav
We study a geometric hitting-set problem in which the input consists of a set of weighted points and a family of axis-parallel segments in the plane. The goal is to…
FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
Fabrizio Grandoni, Anupam Gupta, Jatin Yadav
In the classical Min-Sum Radii problem (MSR) we are given a set of points in a metric space and a positive integer . Our goal is to partition into subsets…
The Landscape of Almost Equitable Allocations
Hadi Hosseini, Vishwa Prakash HV, Aditi Sethia +1
Equitability is a fundamental notion in fair division which requires that all agents derive equal value from their allocated bundles. We study, for general (possibly non-monotone)…
Best-of-Both-Worlds Guarantees with Fairer Endings
Telikepalli Kavitha, Surya Panchapakesan, Rohit Vaish +2
We study best-of-both-worlds guarantees for the fair division of indivisible goods. Prior work has shown that under additive valuations, there always exists a randomized allocation…
Robust-Sorting and Applications to Ulam-Median
Ragesh Jaiswal, Amit Kumar, Jatin Yadav
Sorting is one of the most basic primitives in many algorithms and data analysis tasks. Comparison-based sorting algorithms, like quick-sort and merge-sort, are known to be optimal…
Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities
Salil Gokhale, Harshul Sagar, Rohit Vaish +2
We study the problem of maximizing Nash social welfare, which is the geometric mean of agents' utilities, in two well-known models. The first model involves one-sided preferences,…
FPT Approximation for Capacitated Sum of Radii
Ragesh Jaiswal, Amit Kumar, Jatin Yadav
We consider the capacitated clustering problem in general metric spaces where the goal is to identify clusters and minimize the sum of the radii of the clusters (we call this t…