idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
Eine gemeinsame Pressemitteilung des MPI Mathematik in den Naturwissenschaften und des Exzellenzclusters MATH+.
Michael Joswig, Professor an der TU Berlin, Mitglied des Forschungszentrums der Berliner Mathematik MATH+ und Gruppenleiter am Max-Planck-Institut für Mathematik in den Naturwissenschaften, wurde für die gemeinsam mit Xavier Allamigeon, Pascal Benchimol und Stéphane Gaubert von der École Polytechnique verfasste Arbeit "Log-barrier interior point methods are not strongly polynomial” von der Society of Industrial and Applied Mathematics (SIAM) mit dem renommierten SIGEST-Preis ausgezeichnet. Die Arbeit befasst sich mit einem speziellen Problem zum Lösen linearer Programme.
Die von Michael Joswig gemeinsam mit seinen Kollegen verfasste Arbeit leistet einen
maßgeblichen Beitrag für das Verständnis des neunten Problems auf der sogenannten
Smale-Liste. Der Fields-Medaillist Steven Smale hatte im Jahr 2000 eine Liste von 18
mathematischen Problemen zusammengestellt, die er für wegweisend für die Entwicklung
der Mathematik des 21. Jahrhunderts hielt. Beim Problem mit der Nummer 9 geht es um die
Frage, wie schnell sich lineare Programme genau lösen lassen. Der ausgezeichnete Artikel
erschien nun in einer erweiterten Version in SIAM Review unter der Rubrik SIGEST, für welche pro Quartal ein herausragender Beitrag ausgewählt wird.
Lineare Programme sind zentral für die Lösung komplexer Optimierungsprobleme, sowohl in
der mathematischen Theorie als auch in der wirtschaftlichen Praxis. Beispiele finden sich bei
der Modellierung von Produktionsprozessen oder in der Logistik. Die Herausforderung
besteht darin, auch mit hunderttausenden Variablen und Nebenbedingungen schnell genug
zum Ziel zu gelangen. Michael Joswig konstruiert zur Veranschaulichung folgendes Beispiel
aus der Alltagswelt: „Im Supermarkt möchte ich von n verschiedenen Lebensmitteln jeweils
so viel kaufen, dass mein Tagesbedarf für verschiedene Nährstoffe gedeckt wird. Hierfür
möchte ich so wenig wie möglich investieren. Dieses Optimierungsproblem ist ein lineares
Programm mit n Variablen und m Nebenbedingungen.“
Wegen ihres erheblichen Nutzens sind Algorithmen zur Lösung linearer Programme seit mehr
als 70 Jahren ein intensiv beforschtes Thema an der Grenze zwischen Mathematik und
Informatik. Lineare Programme werden zu jedem Zeitpunkt mindestens millionenfach auf der
Welt gelöst. Der Analyse von Laufzeiten von Algorithmen, beispielsweise implementiert in
Computerprogrammen, kommt eine besondere Bedeutung zu, denn sie garantieren,
benötigte Ergebnisse mit möglichst minimalem Zeitaufwand zu erzielen.
In dieser langen Zeit gab es eine ganze Reihe von bedeutenden Fortschritten. Dennoch
bleibt eine grundsätzliche Frage bis heute offen, die Smale in seinem neunten Problem
aufwirft: Gibt es einen stark polynomialen Algorithmus für die lineare Programmierung?
Joswig und seine Kollegen konnten nachweisen, dass eine der wichtigsten Klassen von LPAlgorithmen, die sogenannten „Log-barrier interior point methods“, dies nicht erfüllen.
Manche Experten hatten genau diese Verfahren bislang als heißeste Kandidaten für eine
positive Lösung betrachtet.
Würde man Smales neuntes Problem auf das genannte Supermarkt-Beispiel anwenden, so
stellt sich die praktische Frage: Wie stark wirkt sich die zusätzliche Berücksichtigung der
Koeffizienten, wie beispielsweise die konkreten Preise der Lebensmittel bzw. deren
Nährstoffgehalt, auf die Laufzeit aus? Die Wissenschaftler wiesen nach, dass die „Log-barrier interior point methods“ unerwarteter Weise viel länger brauchen, wenn die
Preise/Nährstoffgehalte sehr groß werden.
Negative Aussagen in der Komplexitätstheorie sind oft technisch anspruchsvoll, weil sie
erfordern, eine Vielzahl von Algorithmen zu prüfen. Die Beweismethode der Autoren basiert
vor allem auf Methoden aus der tropischen Geometrie, einem aktuellen mathematischen
Forschungsgebiet zwischen Optimierung, algebraischer Geometrie und Kombinatorik. In
Berlin untersucht Michael Joswig im Rahmen des Exzellenzclusters MATH+, ob die in der
ausgezeichneten Arbeit entwickelten tropischen Methoden auch zur Optimierung von
Auktionsverfahren beitragen können (Projekt AA3-5 Tropical Mechanism Design mit Max
Klimm). Die Berliner Mathematik verfügt über in Jahrzehnten aufgebaute Expertise zu
geometrischen Methoden in der linearen Optimierung (Martin Grötschel, Günter M. Ziegler).
Am MPI für Mathematik in den Naturwissenschaften in Leipzig fokussiert sich Joswig derzeit
auf die Entwicklung von Software für die mathematische Forschung, auch in der tropischen
Geometrie.
Die Society for Industrial and Applied Mathematics (SIAM) gibt 18 referierte Fachzeitschriften
heraus, die jedes Jahr insgesamt etwa 1500 wissenschaftliche Arbeiten in allen
Anwendungsbereichen der Mathematik veröffentlichen.
Information zu Professor Michael Joswig
https://page.math.tu-berlin.de/~joswig/
Informationen zur Society of Industrial and Applied Mathematics SIAM:
https://www.siam.org/
Professor Dr. Michael Joswig
E-Mail: joswig@math.tu-berlin.de
- Einstein Professor für Diskrete Mathematik/Geometrie
- Technische Universität Berlin / Institut für Mathematik
- MATH+: Forschungszentrum der Berliner Mathematik
- Max-Planck-Institut für Mathematik in den Naturwissenschaften
Originalpublikation:
Publikation in SIAM Review 63 / 1:
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert und Michael Joswig
"What tropical geometry tells about the complexity of linear programming"
https://doi.org/10.1137/20M1380211
Einführung in den Artikel durch die Herausgeber:
https://epubs.siam.org/doi/abs/10.1137/21N975187
https://www.mis.mpg.de/de.html - Max-Planck-Institut für Mathematik in den Naturwissenschaften (MiS) in Leipzig
https://mathplus.de/ - Exzellenzcluster MATH+: Forschungszentrum der Berliner Mathematik
Menge der zulässigen Lösungen eines linearen Programms (links), einer logarithmischen Deformation (M ...
M. Joswig/T. Brysiewi (MPI-MiS)
© M. Joswig / T. Brysiewicz (MPI Mathematik in den Naturwissenschaften)
Pressemitteilung - SIAM-SIGEST Auszeichnung für Michael Joswig und Kollegen
Merkmale dieser Pressemitteilung:
Journalisten, Studierende, Wissenschaftler
Mathematik
überregional
Wettbewerbe / Auszeichnungen, Wissenschaftliche Publikationen
Deutsch
Menge der zulässigen Lösungen eines linearen Programms (links), einer logarithmischen Deformation (M ...
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).
