Shi Li, Nanjing University

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.

See: https://theory.cs.rutgers.edu/theory_seminar