![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Gil Kalai (Yale) 
Monday 15 April 2024, 13:00-14:00
Understanding linear programming and the simplex algorithm
- đ¤ Speaker: Gil Kalai (Yale) đ Website
- đ Date & Time: Monday 15 April 2024, 13:00 - 14:00
- đ Venue: Computer Laboratory, William Gates Building, LT1
Abstract
Linear programming is the problem of maximizing a linear function Ī subject to a system of linear inequalities. The solutions to these linear inequalities form a convex polyhedron P and Dantzig’s simplex algorithm from the early 50s, can be described geometrically as moving from one vertex to an adjacent vertex of P. I will overview some developments regarding linear programming and the simplex algorithms and present some outstanding problems. The first is bounding from above the diameter of graphs of polytopes and the second is finding pivot rules to the simplex algorithm that require a small number of steps.
Series This talk is part of the Algorithms and Complexity Seminar series.
Included in Lists
- Algorithms and Complexity Seminar
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- Computer Laboratory, William Gates Building, LT1
- Department of Computer Science and Technology talks and seminars
- Interested Talks
- School of Technology
- Trust & Technology Initiative - interesting events
- yk449
Note: Ex-directory lists are not shown.