Nash Social Welfare and A Tale of Mathematical Programs
10Mohit Singh (Georgia Institute of Technology)
https://simons.berkeley.edu/talks/mohit-singh-georgia-institute-technology-2023-11-28
Optimization and Algorithm Design
In the determinant maximization problem, given a collection of vectors, we aim to pick a subset to maximize the determinant of a natural matrix associated with these vectors. The abstract problem captures problems in multiple areas including machine learning, statistics, convex geometry, Nash social welfare problem from algorithmic game theory and network design problems. We will survey the known results and techniques for the problem. The results vary from arbitrary good approximations to only estimation algorithms. The techniques used in these works vary from geometry of polynomials, sparse solutions to convex programming solutions to matroid intersection algorithms. In this talk, we will focus on matroid intersection methods and its connections to the determinant maximization problem.