Einstein-Professor Michael Joswig von der Technischen Universität Berlin wurde für die gemeinsam mit Xavier Allamigeon, Pascal Benchimol und Stéphane Gaubert von der École Polytechnique bei Paris 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 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 Max-Planck Institut 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.
Ansprechpartner:
Einstein-Professor Michael Joswig
joswig@math.tu-berlin.de
Institut für Mathematik
Technische Universität Berlin
Sekretariat MA 6-2
Straße des 17. Juni 136
10623 Berlin
Quelle: gemeinsame Pressemitteilung des MPI Mathematik in den Naturwissenschaften und des Exzellenzclusters MATH+.
