Proportional packing and its dual: previous algorithms
4
The primal problem: exponential reparametrization and objective function
5
The primal problem: not the usual barrier function
6
The primal problem: Linear coupling in one side
7
The primal problem: Conclusion
8
The dual problem: The centroid map
9
The dual problem: A packing linear feasibility problem
10
The dual problem: Adaptive PST oracle
11
A potential application: The Yamnitski-Levin algorithm
12
Bibliography & questions
Description:
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