State of the Art Linear Programming Theory
Doctoral Privatissimum
Basic Information
| Given by: | Andreas Karrenbauer |
|---|---|
| Assistant: | Ruben Becker |
| Time: | Tuesday, 10:15 AM |
| Room: | Rotunda on 2nd floor of the MPII building (E1.4) |
| First Meeting: | April, 19 |
| Credits: | 6 credit points |
| Prerequisites: | This course is a doctoral privatissimum and thus only doctoral students within the graduate school of computer science can participate. For more information concerning doctoral privatissima, see here. In order to participate, you should bring a very good background in algorithms and data structures, as well as a good knowledge of basic math. |
Description
We will read the recent paper (series) by Lee and Sidford. This work constitutes the recent breakthrough in the theory of linear programming. See the references section for links to the papers. At the end of the doctoral privatissimum, we will have understood these results in detail. In order to participate in the seminar, please apply by sending your name, matriculation number, a transcript of records as well as a motivational statement of at most 500 characters to Andreas.
References
| [FOCS14] | Yin Tat Lee and Aaron Sidford | Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow |
| [ArXiv1] | Yin Tat Lee and Aaron Sidford | Path Finding I: Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves |
| [ArXiv2] | Yin Tat Lee and Aaron Sidford | Path Finding II: An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem |