4 papers · 1 filter
A Better-than- Approximation Algorithm for Nash Social Welfare under Additive Valuations
Vignesh Viswanathan
We present an -approximation algorithm for maximizing Nash social welfare under additive valuations, for some constant . This result improves upon the previou…
Some Improved Results on Fair and Balanced Graph Partitions
Vignesh Viswanathan
We consider the problem of partitioning an undirected graph (representing a social network) over nodes and max degree into equally sized parts. Each node in the graph,…
Improved Hardness Results for Nash Social Welfare, Budgeted Allocation and GAP via the Unique Games Conjecture
Vignesh Viswanathan
We consider the problem of dividing a set of indivisible goods among agents with additive valuations. This problem has been studied under various objectives in both the computer sc…
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…