From the 1 of 5 linked papers with an AI index.
5 papers
A Better-than- Approximation Algorithm for Nash Social Welfare under Additive Valuations
Vignesh Viswanathan
The paper proposes an algorithm that achieves a (e^{1/e} − c) approximation, improving on the previous e^{1/e} bound, for maximizing Nash social welfare with additive valuations.
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…
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 -approximate…
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,…
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…