Mathe-Doktorand Oliver Friedmann beweist, dass die "Zadeh-Regel" für die lineare Optimierung "exponentiell" ist.

Oliver Friedmann 250 A1 LMU 2011

(Foto: Eddie Kim)

"Lineare Optimierung" beschreibt einen Typ von ausgesprochen wichtigen Rechenaufgaben, der in allen großen Planungsprozessen auftaucht. Solche Probleme werden üblicherweise mit dem "Simplex-Verfahren" gelöst, das üblicherweise schnell arbeitet, manchmal aber auch ärgerlich lange braucht. Wie schnell es geht, hängt ganz entscheidend von einer Suchvorschrift ab, die in dem Verfahren die Einzelentscheidungen trifft, der "Pivot-Regel". Von den meisten Pivot-Regeln weiß man, dass sie bei manchen Rechenaufgaben sehr langsam sein können. Für die "Zadeh-Regel" wusste man das bisher nicht.

Oliver Friedmann, Doktorand in der Informatik an der LMU München, hat den Beweis gefunden, dass die "Zadeh-Regel" für die lineare Optimierung "exponentiell" ist, also sehr lange zur Problemlösung brauchen kann. Vor dreißig Jahren, 1980, hatte Norman Zadeh als Postdoc an der Stanford University einen Aufsatz über schwierige Beispiele für das Simplexverfahren geschrieben. Der Aufsatz ist nie in einer Zeitschrift erschienen, gehört aber zu den Klassikern der Mathematischen Optimierung. Damals, als Zadeh noch nicht reich war, hat er ein Preisgeld von 1000 US-Dollar ausgesetzt - für einen Beweis, dass die "least entered" Pivot-Regel, die in dem Aufsatz vorgeschlagen wurde, langsam sein kann - oder für den Beweis des Gegenteils.

Auf einem Workshop am 20. Januar 2011 im IPAM, dem "Institute for Pure and Applied Mathematics" an der UCLA (University of California at Los Angeles) hat Oliver Friedmann nun die Lösung des Problems vorgestellt: die Zadeh-Regel kann quälend langsam sein! Und Norman Zadeh kam, um Friedmann einen Scheck von 1000 \( für die Lösung des Problems zu überreichen. Der Aufsatz von Oliver Friedmann ist neu und natürlich noch nicht im Detail überprüft. Er ist aber zur Vorstellung auf der renommierten IPCO-Konferenz 2011 angenommen worden. Bis zur endgültigen Überprüfung der Problemlösung soll Prof. Günter M. Ziegler als ehemaliger Präsident der Deutschen Mathematiker-Vereinigung den 1000\)-Scheck von Norman Zadeh in Obhut nehmen...

Zum Blogeintrag von Günter M. Ziegler.