Francisco Criado - The Dual 1-Fair Packing Problem and Applications to Linear Programming

Francisco Criado - The Dual 1-Fair Packing Problem and Applications to Linear Programming

Explore a 26-minute lecture on the dual 1-fair packing problem and its applications to linear programming. Delve into proportional fairness, a resource allocation scheme introduced by Nash in 1950, and its relevance to network flows. Examine the Lagrange dual of the 1-fair packing problem and its connection to Yamnitsky and Levin's "simplices" algorithm. Learn about the geometric relationship between primal and dual problems, and discover how this insight leads to a faster algorithm for the dual problem. Gain insights into potential improvements for the Yamnitsky and Levin algorithm through this joint work by Francisco Criado, Prof. Dr. Sebastian Pokutta, and David Martínez.