Short Simplex Paths in Lattice Polytopes

on YouTube ↗31m

" summary

Algorithms produce explicit simplex edge paths on lattice polytopes in a box, with a first constructive method giving a path length bounded roughly by n^4 · K · log K (independent of the number of inequalities and of the cost vector) using bit-scaling plus a Franke Tardos preprocessing, and a second iterative method that peels off one equality per iteration to reduce dimension and improves the bound to roughly n^2 (with the entry-size α appearing only inside logs). Both are implemented as oracle-based pivoting routines and provably terminate.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 1:48Diameter of lattice polytopes
3. 5:21LP on lattice polytopes
4. 7:38How "short" can a simplex path be?
5. 9:45Short simplex paths in lattice polytopes
6. 12:40How does it work?
7. 14:39Basic algorithm
8. 21:51Preprocessing & scaling algorithm
9. 22:09Iterative algorithm
10. 27:22Correctness - idea
11. 29:11Short simplex paths - idea