Die Simplex-Lösung

Während er in einem Gerichtssaal saß und darauf wartete herauszufinden, ob er für die Jury ausgewählt werden würde, hatte Daniel Spielman eine Offenbarung – die ganze Arbeit, die er und sein Kollege Shanghua Teng in den letzten drei Jahren aufgebaut hatten, war ein Kartenhaus. Ich werde es nie vergessen, sagt Spielman, außerordentlicher Professor für Mathematik. Da saß ich da und wartete - zum Glück nicht ausgewählt zu werden – ich hatte die schreckliche Erfahrung, zu erkennen, dass alles, was wir getan hatten, falsch war. Ich dachte daran, mein Forschungsprogramm wegzuwerfen. Und in diesem Moment brachen die Karten zusammen.

Das Paar hatte versucht, einen Weg zur Verbesserung der Simplex-Methode zu finden, einem der am weitesten verbreiteten Algorithmen der Welt. Sie ermöglicht es, dass viele der für uns selbstverständlichen komplexen Systeme wie Telekommunikationsnetze und Disposition von Lieferfahrzeugflotten oder Fluglinienflügen so effizient und kostengünstig wie möglich arbeiten. Als neuer Assistenzprofessor wollte sich Spielman in der Welt der Mathematik etablieren und am MIT arbeiten, indem er an einer großen Herausforderung arbeitete, nämlich den Algorithmus einfacher, schneller und besser zu machen. Aber nach diesem Tag im Gerichtsgebäude, als er erkannte, dass die Anwendung von Konzepten aus einem nicht verwandten Bereich auf den Simplex-Algorithmus eine Sackgasse war, wusste er, dass er einen weiteren großen Durchbruch finden musste, um seine Ziele zu erreichen.

Ein paar Tage später begann Spielman, wie ein Mensch, dessen Haus von einem Hurrikan oder Tornado zerstört wurde, zu retten, was von seiner ruinierten Forschung übrig geblieben war. Und da kam die ganz große Idee: Seine Arbeit konnte die Simplex-Methode zwar nicht verbessern, aber vielleicht doch erkläre es . Die Methode wurde 1947 entwickelt, aber nach mehr als 50 Jahren Analyse hatte niemand herausfinden können, warum sie funktionierte. Spielmans Vermutung erwies sich als richtig. Nach weiteren drei Jahren gemeinsamer Arbeit und Hunderten mathematischer Formeln können er und Teng, Professor an der Boston University, nun erklären, warum die Simplex-Methode funktioniert. Dadurch können die sogenannten Optimierungsexperten möglicherweise noch komplexere organisatorische Probleme lösen. Die als geglättete Analyse bezeichnete Erklärung wurde bereits von der National Science Foundation als großer Fortschritt in der Informationstechnologie bezeichnet.



Der Weg zur Entdeckung

Karte unserer Galaxie

Spielman und Teng trafen sich zum ersten Mal im Herbst 1990, als Spielman, damals noch Student an der Yale University, die Carnegie Mellon University besuchte, um eine Rede zu halten. Teng, Doktorand dort, sagt, er und andere an der Universität hätten den langhaarigen College-Junior bewundert. Er hatte bereits zwei Dissertationen von Doktortitel. Natürlich war er einer der begehrtesten Studieninteressierten, die alle Top-Universitäten für ihre PhD-Programme gewinnen wollten. 1992 entschied sich Spielman für das MIT. Teng kam im selben Jahr als Ausbilder an das Institut. Aus der Schüler-Lehrer-Beziehung wurde bald eine Freundschaft und dann eine Zusammenarbeit, die 11 Jahre dauerte.

1996, nach mehreren Jahren der Zusammenarbeit auf einem anderen Gebiet, begann das Duo, die Simplex-Methode zu verbessern. Der Prozess der Recherche ähnelt dem Versuch, mit einer kleinen Taschenlampe einen Schatz auf einer dunklen Insel zu finden, sagt Teng. Wir haben versucht, diese vielen hoffnungsvollen Hinweise zu erkunden. Dan führt immer ausführliche Arbeitstagebücher, die die Karten der Erkundung systematisch markieren.

Feng-Zhang-Nobelpreis

Nach drei Jahren solcher Arbeit hatte Spielman seine Gerichtssaal-Realisierung. Die beiden Mathematiker änderten ihr Ziel und gingen das neue Forschungsproblem ernsthaft an.

Teng, der zu diesem Zeitpunkt außerordentlicher Professor an der University of Illinois in Urbana-Champaign war, zog für ein Sabbatical zurück nach Massachusetts und mietete eine Wohnung fünf Minuten von Spielmans entfernt. Danach verwandelten die beiden Forscher ihre Wohnzimmer in Arbeitsräume. Teng befestigte ein großes Whiteboard an seiner Wohnzimmerwand. Spielman bewahrte einen hinter seinem Sofa auf.

Von da an fand ihre gemeinsame Arbeit rund um die Uhr statt. Es war eines dieser Dinge, bei denen sich meine Frau darüber beschwerte, dass ich Shanghua seit einigen Jahren häufiger sah als ich sie sah, sagt Spielman. Teng arbeitete Vollzeit bei Akamai in Cambridge, aber er ging fast jede Nacht nach der Arbeit und am Wochenende zu Spielmans Wohnung. Wir würden viele Stunden wach bleiben, wahrscheinlich bis zwei, arbeiten, bemerkt Spielman. Teng fügt hinzu, ich war wie ein adoptiertes Mitglied von Dans Familie. Sogar ihre Katze Chloe hat sich so an unsere Anwesenheit gewöhnt, dass sie sich vor das Whiteboard setzte und aufmerksam zusah, wenn wir es aufstellten. Die Forscher bedankten sich bei Chloe in der Danksagung für ihre Zeitschriftenarbeit.

Glühen im Dunkeln Hund Crispr

Um den Überblick über ihre Arbeit zu behalten, führte Spielman seine Arbeitstagebücher fort und schrieb jeden Gedanken und jede Gleichung auf den Whiteboards auf, bevor er sie löschte. Heute säumen ein Dutzend dieser 200-seitigen Zeitschriften in Notizbuchgröße ein Bücherregal in seinem Büro in Gebäude 2. Er sagt, dass etwa 60 Prozent der Informationen, die die Zeitschriften enthalten, an geglätteten Analysen arbeiten. Währenddessen machte Teng mit einer Digitalkamera etwa 40 Fotos der Whiteboards, bevor sie gelöscht wurden.

Endlich beantworten warum

Das Ergebnis all dieser Forschungen war die Antwort auf die einfache Frage Warum? Spielman und Teng haben endlich herausgefunden, warum die Simplex-Methode die ganze Zeit so gut funktioniert hat. Sie taten dies, indem sie eine neue Methode zur Analyse des Algorithmus entwickelten.

Bis zu ihrer Entdeckung haben die meisten Mathematiker Algorithmen mit der Worst-Case-Analyse gemessen, bei der einem Algorithmus die schwierigsten Daten gegeben und dann beurteilt wird, wie gut er damit rechnen kann. Es wäre, als ob Ihnen jemand das denkbar schlechteste Langteilungsproblem in die Hand drückt und dann testet, ob Sie es lösen können und wie lange es dauern würde. Aber das hat mit der Simplex-Methode einfach nicht funktioniert.

Übersetzung vom Englischen ins Spanische mit Audio

Also fanden Spielman und Teng einen neuen Ansatz. Sie führten eine gewisse Variabilität in die Worst-Case-Analyse ein. Anstatt genaue Zahlen als Eingaben zu verwenden, um den Algorithmus zu testen, ließen sie Ungenauigkeiten zu. Wenn die Eingabe beispielsweise 1,31 war, erlaubten sie eine zufällige Eingabe zwischen 1,29 und 1,33. Sie fanden heraus, dass der Simplex-Algorithmus das Problem immer effizient löste, indem er Ungenauigkeiten berücksichtigte, und deshalb so erfolgreich war.

Die Idee klingt einfach, aber die Mathematik, die sie unterstützt, ist komplex. Spielmans und Tengs erster Zeitschriftenartikel zu diesem Thema, der jetzt von der Association for Computing Machinery’s begutachtet wird Zeitschrift der ACM , enthält 80 Seiten mit Gleichungen. Ich weiß nicht, ob so viele Leute durch die Zeitung gehen könnten, sagt Spielman. Tatsächlich verwirrte das Schreiben der Zeitung gelegentlich sogar Spielman und Teng. Ein paar Mal haben wir das Geschriebene einfach weggeworfen und neu geschrieben, denn wenn es für uns kompliziert war, wurde es für [andere] Leute noch komplizierter, sagt Spielman.

Spielman und Teng haben ihre Ergebnisse weltweit auf begeisterte Resonanz präsentiert. Sie veröffentlichten 2001 ein Konferenzpapier und haben seitdem eingeladene Präsentationen und Keynote-Vorträge in den Vereinigten Staaten sowie in China, der Türkei, Italien, der Schweiz und Dänemark gehalten.

Diese geglättete Analyse ist eine wichtige Entwicklung, sagt Michel Goemans, PhD '90, ein MIT-Professor für angewandte Mathematik. Und David Johnson, Leiter der Abteilung für Algorithmen und Optimierung bei AT&T Labs-Research, sagt: [Geglättete Analyse] bietet ein zusätzliches Maß an Sicherheit für diejenigen, die die Simplex-Methode verwenden.

Spielman sagt, er habe sein Whiteboard seit letztem Sommer nicht mehr herausgezogen, als die Zeitschriftenarbeit endlich fertig war, aber ohne sie hätten wir es nie geschafft, die Arbeit zu schreiben. Jetzt empfiehlt Spielman jungen Forschern, große Whiteboards zu kaufen, um einen guten ersten Schritt zum Durchbruch zu machen. Teng schreibt jedoch einen großen Teil ihres Erfolgs Spielmans dynamischem Verstand und seinem großen Geschmack bei der Auswahl von Forschungsproblemen zu. Er habe immer den Mut, an dem schwierigsten offenen Problem auf diesem Gebiet zu arbeiten, sagt Teng, und das könnte für Forscher und Neugierige überall ein noch besserer Ausgangspunkt sein.

verbergen

Tatsächliche Technologien

Kategorie

Unkategorisiert

Technologie

Biotechnologie

Technologierichtlinie

Klimawandel

Mensch Und Technik

Silicon Valley

Computer

Mit News Magazine

Künstliche Intelligenz

Platz

Intelligente Städte

Blockchain

Reportage

Alumni-Profil

Alumni-Verbindung

Mit News Feature

1865

Meine Sicht

77 Mass Avenue

Treffen Sie Den Autor

Profile In Großzügigkeit

Auf Dem Campus Gesehen

Lerne Den Autor Kennen

Alumni-Briefe

Nicht Kategorisiert

77 Massenallee

Rechnen

Tech-Richtlinie

Lernen Sie Den Autor Kennen

Nachrichten

Wahl 2020

Mit Index

Unter Der Kuppel

Feuerwehrschlauch

Unendliche Geschichten

Pandemie-Technologieprojekt

Vom Präsidenten

Titelstory

Fotogallerie

Empfohlen