Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations

Start Date: February 5, 2025
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Shi Li - Nanjing University
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p> <p> </p>
Presentation Type: Stand Alone Presentation
Abstract:
In this talk, I will give our recent result on the problem of assigning items to agents so as to maximize the emph{weighted} Nash Social Welfare (NSW) under submodular valuations. Obtaining a constant approximation algorithm for problem is an open problem in the field that has recently attracted considerable attention. We give the first such algorithm for the problem, thus solving the open problem in the affirmative. Our algorithm is based on the natural Configuration LP for the problem, which was introduced recently by Feng and Li cite{FL24} for the additive valuation case. Our rounding algorithm is similar to that of Li cite{Li25} developed for the unrelated machine scheduling problem to minimize weighted completion time.

This is based on joint work with Yuda Feng, Yang Hu and Ruilong Zhang.

Events