Completed
Fast Weakly Polynomial Algorithms for LP
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Revisiting Tardos’s Framework for Linear Programming - Faster Exact Solutions using Approximate Solvers
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Linear Programming
- 3 Weakly vs Strongly Polynomial Algorithms for
- 4 Fast Weakly Polynomial Algorithms for LP
- 5 Strongly Polynomial Algorithms for LP
- 6 Dependence on the constraint matrix only
- 7 Tardos's framework: variable fixing
- 8 Our contributions: Dadush-N.-Végh '20
- 9 The condition number A
- 10 Proximity theorem
- 11 Variable fixing for feasibility
- 12 The lifting operation
- 13 The feasibility algorithm
- 14 Optimization algorithm
