Spring 2019

Discrete Optimization using Log-Concave Polynomials

Wednesday, May 1, 2019 9:30 am10:15 am PDT

Add to Calendar


Nima Anari (Stanford University)

In this talk I will showcase some applications of hyperbolic, and more generally log-concave, polynomials to discrete optimization problems. I will present a framework for approximately finding the maximum of a discrete function on the hypercube as long as this function is associated with coefficients of a log-concave polynomial. I will also discuss finding the maximum of a mixture of function values. Some specific problems solved by this framework include Nash welfare maximization, and determinant/volume maximization subject to a matroid constraint. Based on joint works with Shayan Oveis Gharan, Kuikui Liu, Amin Saberi, Mohit Singh, and Cynthia Vinzant.