Opening Linear Programming: Optimization Reduces to Feasibility
Linear Programming: Optimization Reduces to Feasibility
- Length
- 23 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Search and optimization reductions
Demonstrates how linear programming optimization reduces to feasibility via binary search and continued fractions.
Linear programming search and optimization reduce to feasibility in polynomial time in O'Donnell's graduate CMU 15-750 session. O'Donnell tests coordinate planes to find a point in a polytope and uses continued fractions to recover exact rational solutions.
Linear programming search and optimization reduce to feasibility in polynomial time in O'Donnell's graduate CMU 15-750 session. O'Donnell tests coordinate planes to find a point in a polytope and uses continued fractions to recover exact rational solutions.
This lecture
Lecture 55 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in