5 papers
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…
Equitable Colorings of Vertex-Weighted Graphs
Siddharth Barman, Vignesh Viswanathan
We study a generalization of the classical Hajnal-Szemerédi theorem to vertex-weighted graphs. Given a graph with nonnegative vertex weights, a coloring is called -approximately…
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
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…