Algorithms & Randomness Center (ARC)
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).
----------------------------------
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
