6 papers
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
Fair allocation of indivisible goods is a fundamental problem at the interface of economics and computer science. Traditional approaches focus either on randomized allocations that…
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,…
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…