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.
Francisco Criado - The Dual 1-Fair Packing Problem and Applications to Linear Programming
Hausdorff Center for Mathematics via YouTube
Overview
Syllabus
Intro
alpha-fairness and proportional fairness
Proportional packing and its dual: previous algorithms
The primal problem: exponential reparametrization and objective function
The primal problem: not the usual barrier function
The primal problem: Linear coupling in one side
The primal problem: Conclusion
The dual problem: The centroid map
The dual problem: A packing linear feasibility problem
The dual problem: Adaptive PST oracle
A potential application: The Yamnitski-Levin algorithm
Bibliography & questions
Taught by
Hausdorff Center for Mathematics
