Understanding linear programming and the simplex algorithm

Add to your list(s) Download to your calendar using vCal

• Gil Kalai (Yale)
• Monday 15 April 2024, 13:00-14:00
• Computer Laboratory, William Gates Building, LT1.

If you have a question about this talk, please contact Tom Gur.

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.

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• 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
• bld31
• ki287

Note that ex-directory lists are not shown.