Seminars

View all Seminars  |  Download ICal for this event

Improved Hardness Results for Nash Social Welfare, Budgeted Allocation and GAP via the Unique Games Conjecture

Series: Bangalore Theory Seminars

Speaker: Vignesh Viswanathan, University of Massachusetts Amherst,

Date/Time: Jun 05 18:00:00

Location: Online Talk (See Teams link below)

Abstract:
My talk will be about 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 science and the operations research literature. In this talk, I will present a novel dictator test using this problem, which can separate a dictator from any function sufficiently far from a dictator. I will then show how this test can be used to prove the following hardness results (assuming the unique games conjecture is true):
(1) It is NP-hard to approximate the max Nash welfare by a factor better than 1.0761. This improves on the previous best known inapproximability factor of 1.069.
(2) It is NP-hard to approximate the maximum budgeted allocation by a factor better than 1.07. This improves on the previous best known inapproximability factor of 1.067.
(3) It is NP-hard to approximate the max generalized assignment problem (GAP) by a factor better than 1.124. This improves on the previous best known inapproximability factor of 1.10.


Microsoft teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan