# With Number 9 to the Prestigious SIGEST Award

Joint press release by Max Planck Institute for Mathematics in the Sciences (MiS) and MATH+: The Berlin Mathematics Research Center.

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 research deals with a special problem for solving linear programs.

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/

**Contact for scientific information:**

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

**Original publication:**

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

**More information:**

https://www.mis.mpg.de/ - Max Planck Institute for Mathematics in the Sciences (MiS)

https://mathplus.de/ - MATH+: The Berlin Mathematics Research Center