3 papers
cs.GT2026
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…
cs.GT2026
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,…
cs.GT2025
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…