Jan van den Brand (Simons-Berkeley)

Wednesday, September 22, 2021

Klaus 1116 East - 3:00 pm

Title:  From Interior Point Methods to Data Structures and Back

Abstract: Linear Programs (LPs) capture many optimization problems such as shortest paths or bipartite matching. In the past years, there have been substantial improvements for LP solvers, resulting in algorithms that run in nearly linear time for dense LPs. This also led to a nearly linear time algorithm for bipartite matching on dense graphs. In this talk, I will explain how these improvements stem from an interplay of interior point methods and dynamic algorithms (data structures).

----------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836

Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu