Title: A Polynomial Time Algorithm to Solve a Class of Optimization Problems with a Multi-linear Objective Function and Affine Constraints

Speaker: Hadi Charkhgard
Abstract: 

In this talk, I will present the first polynomial-time linear programming based algorithm for a class of optimization problems with a multi-linear objective function and affine constraints. This class of optimization problems arises naturally in a number of settings in game theory, such as the bargaining problem, linear Fisher markets, and Kelly capacity allocation markets, but has applications in other fields of study as well. The algorithm computes an optimal solution by solving at most O(p^3) linear programs, where p is the number of variables in the multi-linear objective function.