Michael Joswig, professor at TU Berlin, member of the Berlin Mathematics Research Center MATH+ and group leader at the Max Planck Institute for Mathematics in the Sciences, was awarded the prestigious SIGEST award by the Society of Industrial and Applied Mathematics (SIAM) for the paper “Log-barrier interior point methods are not strongly polynomial”, co-authored with Xavier Allamigeon, Pascal Benchimol and Stéphane Gaubert from École Polytechnique. The paper, which deals with a special problem for solving linear programs, is considered one of the most outstanding recent articles in the SIAM journals. 

The paper by Michael Joswig and his colleagues contributes significantly to investigating the ninth problem on the so-called Smale list. In 2000, Fields Medalist Steven Smale compiled a list of 18 mathematical problems that he believed were groundbreaking for the development of mathematics in the 21st century. The problem number 9 is about how quickly linear programs can be solved exactly. The award-winning article has now appeared in an expanded version in the SIGEST section of SIAM Review, for which one outstanding paper is selected each quarter, under the title: “What Tropical Geometry Tells Us about the Complexity of Linear Programming”.

In Berlin, as part of the Cluster of Excellence MATH+, Michael Joswig is investigating whether the tropical methods developed in the awarded paper can also contribute to the optimization of auction processes (project AA3-5 Tropical Mechanism Design with Max Klimm). Berlin mathematics has decades of great expertise in geometric methods in linear optimization (Martin Grötschel, Günter M. Ziegler). At the MPI for Mathematics in the Sciences in Leipzig, Joswig is currently focusing on the development of software for mathematical research, tropical geometry included.

Read the joint press release of MPI MiS and MATH+ in English

MPI MiS and MATH+ joint press release in German

Publication in SIAM Review 63 / 1 

Introduction to the article by the authors