Leonid Khachiyan - Leonid Khachiyan

Leonid Khachiyan
Leonid Khachiyan.jpg
Geboren ( 1952-05-03 )3. Mai 1952
Leningrad , Russische SFSR , Sowjetunion
Ist gestorben 29. April 2005 (2005-04-29)(Alter 52)
Staatsangehörigkeit Armenisch
Staatsbürgerschaft Sowjetunion, Vereinigte Staaten
Auszeichnungen Fulkerson-Preis (1982)
Wissenschaftlicher Werdegang
Institutionen Rechenzentrum der Sowjetischen Akademie der Wissenschaften
Rutgers University

Leonid Genrichovic Khachiyan ( / k ɑː í ən / ; Russisch : Леонид Генрихович Хачиян , 3. Mai 1952 - 29. April 2005) war ein sowjetischer und amerikanischer Mathematiker und Informatiker .

Er war am bekanntesten für seinen Ellipsoid-Algorithmus (1979) für die lineare Programmierung , der der erste solcher Algorithmus war, von dem bekannt war, dass er eine polynomielle Laufzeit hatte. Obwohl sich dieser Algorithmus als unpraktisch erwiesen hat, hat er andere randomisierte Algorithmen für die konvexe Programmierung inspiriert und gilt als bedeutender theoretischer Durchbruch.

Frühes Leben und Ausbildung

Khachiyan wurde am 3. Mai geboren 1952 in Leningrad zu Armenian Eltern Genrikh Borissowitsch Khachiyan, Mathematiker und Professor für theoretische Mechanik und Zhanna Saakovna Khachiyan, ein Bauingenieur . Seine Großeltern waren Karabach- Armenier. Er hatte zwei Brüder: Boris und Yevgeniy (Eugene). 1961, als er neun Jahre alt war, zog seine Familie nach Moskau . Er erhielt einen Master-Abschluss vom Moskauer Institut für Physik und Technologie . 1978 erwarb er seinen Ph.D. in Computermathematik / Theoretischer Mathematik vom Computerzentrum der Sowjetischen Akademie der Wissenschaften und 1984 einen D.Sc. in Informatik an derselben Institution.

Karriere

Khachiyan begann seine Karriere an der Sowjetischen Akademie der Wissenschaften und arbeitete als Forscher am Computerzentrum der Akademie in Moskau. Außerdem war er als außerordentlicher Professor am Moskauer Institut für Physik und Technologie tätig . 1979 erklärte er: "Ich bin theoretischer Mathematiker und arbeite gerade an einer Klasse sehr schwieriger mathematischer Probleme." Khachiyan wanderte 1989 in die USA aus. Er lehrte zunächst als Gastprofessor an der Cornell University . 1990 wechselte er als Gastprofessor an die Rutgers University . 1992 wurde er Professor für Informatik an der Rutgers. Bis 2005 war er Professor II an der Rutgers.

Arbeiten an linearer Programmierung

Ellipsoid-Methode

Khachiyan ist am bekanntesten für sein vierseitiges Papier vom Februar 1979, das zeigte, wie ein Ellipsoidverfahren für die lineare Programmierung in polynomieller Zeit implementiert werden kann. Das Papier wurde in mehrere Sprachen übersetzt und verbreitete sich ungewöhnlich schnell auf der ganzen Welt. Die Autoren einer 1981 veröffentlichten Übersicht über seine Arbeit stellten fest, dass sie "große Aufregung und eine Flut von Fachartikeln ausgelöst hat" und von großen Zeitungen behandelt wurde. Es wurde ursprünglich ohne Korrekturen veröffentlicht, die von Khachiyan in einem späteren Artikel, der 1980 veröffentlicht wurde, und von Peter Gács und Laszlo Lovász im Jahr 1981 vorgelegt wurden im August 1979. Es wurde weiter populär, als Gina Kolata am 2. November 1979 im Science Magazine darüber berichtete .

Khachiyans Theorie gilt als bahnbrechend, die "das Gebiet der linearen Programmierung vorangebracht hat". Giorgio Ausiello bemerkte, dass die Methode nicht praktikabel sei, "aber es war ein echter Durchbruch für die Welt des Operations Research und der Informatik, da sie bewies, dass die Entwicklung von polynomialen Zeitalgorithmen für die lineare Programmierung möglich war und tatsächlich den Weg zu anderen öffnete". , praktischere Algorithmen, die in den folgenden Jahren entwickelt wurden."

Persönliches Leben und Sterben

Khachiyan sprach Russisch und Englisch, aber kein Armenisch . Bahman Kalantari bemerkte: "Für einige war sein englischer Akzent nicht immer leicht zu verstehen." Das New York Times- Profil von 1979 beschrieb Khachiyan als "einen entspannten, freundlichen jungen Mann in einem Pullover, der ein wenig Englisch spricht, das er in der High School gelernt hat".

Bei seinen Freunden und Kollegen war er als "Leo" und "Lenya" bekannt. Václav Chvátal beschrieb ihn als „selbstlos, offen, geduldig, mitfühlend, verständnisvoll, rücksichtsvoll“. Michael Todd, ein anderer Kollege, beschrieb ihn als "politisch zynisch", "sehr bescheiden und freundlich zu seinen Freunden" und "intolerant gegenüber Herablassung und Pompösität".

Khachiyan heiratete 1985 Olga Pischikova Reynberg, russisch-jüdischer Herkunft. Sie hatten zwei Töchter, Anna und Nina, die zum Zeitpunkt seines Todes noch Teenager waren. Im Jahr 2000 wurde er eingebürgerter US-Bürger. Er starb am 29. April 2005 im Alter von 52 Jahren in South Brunswick, New Jersey, an einem Herzinfarkt .

Erkennung

1982 erhielt er den renommierten Fulkerson-Preis der Mathematical Programming Society und der American Mathematical Society für herausragende Arbeiten auf dem Gebiet der diskreten Mathematik, insbesondere für seinen 1979 erschienenen Artikel "A polynomial algorithm in linear Programming".

Khachiyan galt als "anerkannter Experte der Informatik, dessen Arbeit Computern half, äußerst komplexe Probleme zu verarbeiten". Zum Zeitpunkt seines Todes wurde er von Haym Hirsh, dem Vorsitzenden der Informatikabteilung bei Rutgers, als einer der berühmtesten Informatiker der Welt bezeichnet. "Informatiker und Mathematiker sagen, dass seine Arbeit dazu beigetragen hat, sein Fachgebiet zu revolutionieren", schrieb er in seinem Nachruf in der New York Times . Bahman Kalantari, ein Freund und Kollege bei Rutgers, schrieb: "Khatschiyan wird sicherlich immer zu den größten und legendärsten Persönlichkeiten auf dem Gebiet der mathematischen Programmierung gehören."

Verweise

Anmerkungen
Zitate

Externe Links