With Number 9 to the SIGEST Award

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.

Linear programs are crucial for the solution of complex optimization problems, both in mathematical theory as well as in economy. Examples can be found in the modeling of whole production processes or in logistics. The challenge is to reach the goal quickly enough, even with hundreds of thousands of variables and constraints. To illustrate the problem, Michael Joswig constructs the following example from everyday life: “In the supermarket, I want to buy enough of n different foods that my daily requirement for m different nutrients is covered. I want to invest as little as possible for them. This optimization problem is a linear program with n variables and m constraints.”

Because of their considerable benefits, algorithms for solving linear programs have been an intensively researched topic on the border between mathematics and computer science for more than 70 years. Linear programs are solved at least a million times in the world at any given time. The analysis of running times of algorithms, for example implemented in computer programs, is of special importance, because it guarantees to achieve the required results with the least possible expenditure of time.

There have been quite a number of significant advances in this long period. Nevertheless, a fundamental question remains open to this day, which Smale raises in his ninth problem: Is there a strongly polynomial algorithm for linear programming? Joswig and his colleagues were able to prove that one of the most important classes of LP algorithms, the so-called “log-barrier interior point methods”, does not meet this requirement. Some experts had previously considered precisely these very procedures to be the hottest candidates for a positive solution.

If one were to apply Smale's ninth problem to the aforementioned supermarket example, the question would be: How much does the additional consideration of coefficients, such as the specific prices of the groceries or their nutrient content, affect the running time? The scientists demonstrated that the “log-barrier interior point methods” unexpectedly take much longer when the prices/nutrient contents become very high.

Negative statements in complexity theory are often technically demanding because they require a large number of algorithms to be considered. The authors' method of proof is based primarily on methods from tropical geometry, a current area of mathematical research between optimization, algebraic geometry, and combinatorics.

In Berlin, as part of the Cluster of Excellence MATH+, Michael Joswig is investigating the 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.

The Society for Industrial and Applied Mathematics (SIAM) publishes 18 peer-reviewed journals which release a total of around 1500 scientific papers each year in all fields of mathematical research.