With Number 9 to the Prestigious SIGEST Award

Hinweis zur Verwendung von Bildmaterial: Die Verwendung des Bildmaterials zur Pressemitteilung ist bei Nennung der Quelle vergütungsfrei gestattet. Das Bildmaterial darf nur in Zusammenhang mit dem Inhalt dieser Pressemitteilung verwendet werden. Falls Sie das Bild in höherer Auflösung benötigen oder Rückfragen zur Weiterverwendung haben, wenden Sie sich bitte direkt an die Pressestelle, die es veröffentlicht hat.

Picture: Set of feasible solutions of a linear program (left), a logarithmic deformation (center), and the tropical limit (right). | Quelle: M. Joswig/T. Brysiewi (MPI-MiS) | Copyright: © M. Joswig/T. Brysiewicz (MPI Mathematik in den Naturwissenschaften) | Download

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 form 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.

Information about Professor Michael Joswig
https://page.math.tu-berlin.de/~joswig/

Information about the Society of Industrial and Applied Mathematics (SIAM):
https://www.siam.org/

Wissenschaftlicher Ansprechpartner:
Professor Michael Joswig
Email: joswig@math.tu-berlin.de
- Einstein Professor for Discrete Mathematics / Geometry
- Technical University of Berlin / Mathematical Institute
- MATH+: The Berlin Mathematics Research Center
- Max Planck Institute for Mathematics in the Sciences, Leipzig

Originalpublikation:
Publication in SIAM Review 63 / 1:
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig
"What tropical geometry tells about the complexity of linear programming"
https://doi.org/10.1137/20M1380211

Introduction to the article by the authors:
https://epubs.siam.org/doi/abs/10.1137/21N975187

Weitere Informationen:
https://www.mis.mpg.de/ - Max Planck Institute for Mathematics in the Sciences (MiS)
https://mathplus.de/ - MATH+: The Berlin Mathematics Research Center