idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
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/
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
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
https://www.mis.mpg.de/ - Max Planck Institute for Mathematics in the Sciences (MiS)
https://mathplus.de/ - MATH+: The Berlin Mathematics Research Center
Picture: Set of feasible solutions of a linear program (left), a logarithmic deformation (center), a ...
M. Joswig/T. Brysiewi (MPI-MiS)
© M. Joswig/T. Brysiewicz (MPI Mathematik in den Naturwissenschaften)
Press Release - SIAM-SIGEST Award for Michael Joswig and Colleagues
Merkmale dieser Pressemitteilung:
Journalisten, Studierende, Wissenschaftler
Mathematik
überregional
Wettbewerbe / Auszeichnungen, Wissenschaftliche Publikationen
Englisch
Picture: Set of feasible solutions of a linear program (left), a logarithmic deformation (center), a ...
M. Joswig/T. Brysiewi (MPI-MiS)
© M. Joswig/T. Brysiewicz (MPI Mathematik in den Naturwissenschaften)
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
