idw – Informationsdienst Wissenschaft

Nachrichten, Termine, Experten

Grafik: idw-Logo
Thema Corona

Science Video Project
idw-News App:


01.03.2021 14:57

With Number 9 to the Prestigious SIGEST Award

Beate Rogler MATH+, Presse- und Öffentlichkeitsarbeit, Sekretariat MA 2-2
MATH+ Das Forschungszentrum der Berliner Mathematik

    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

    Information about the Society of Industrial and Applied Mathematics (SIAM):

    Wissenschaftliche Ansprechpartner:

    Professor Michael Joswig
    - 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"

    Introduction to the article by the authors:

    Weitere Informationen: - Max Planck Institute for Mathematics in the Sciences (MiS) - MATH+: The Berlin Mathematics Research Center

    attachment icon Press Release - SIAM-SIGEST Award for Michael Joswig and Colleagues

    Merkmale dieser Pressemitteilung:
    Journalisten, Studierende, Wissenschaftler
    Wettbewerbe / Auszeichnungen, Wissenschaftliche Publikationen

    Picture: Set of feasible solutions of a linear program (left), a logarithmic deformation (center), and the tropical limit (right).

    Zum Download



    Die Suche / Erweiterte Suche im idw-Archiv

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