On The Polyhedral Geometry Of Pivot Rules

on YouTube ↗57m

" summary

Constructs a concrete polytope that parametrizes how local, memoryless pivot rules vary: the pivot rule polytope records when two weight choices yield the same arborescence and proves it is a Minkowski sum of simplices. Defines and studies normalized weight (NW) rules, shows the shadow-vertex method admits a max-slope generalization that is memoryless, and uses polyhedral and parametric LP tools to bound the number of coherent arborescences (simplex case gives Catalan many coherent outcomes).

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 2:05Linear Programs
3. 5:51Pivot Rules
4. 17:22Normalized Weight Pivot Rules
5. 27:09Pivot Polytope
6. 30:49Shadow Vertex Rule
7. 32:44Max Slope Rule
8. 35:29Shadow Vertex
9. 40:09Monotone Path
10. 43:49Simplex Example
11. 45:24Parametric Linear Programming
12. 47:19Reflection Groups
13. 54:09Random perturbations