Smoothed analysis of the simplex method

Sophie Huiberts (Columbia University in NYC)

04-May-2023, 14:15-16:00 (11 months ago)

Abstract: The simplex method is a combinatorial algorithm for solving linear optimization problems. The algorithm is very efficient in practice, but theoretical explanations of this fact are lacking. In this talk, I will describe one of the primary theoretical frameworks for analysing the simplex method, smoothed analysis, and present upper and lower bounds on the algorithm's running time.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic


Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456

Organizers: Karim Adiprasito, Arina Voorhaar*
*contact for this listing

Export talk to