Nekrolog: Tajemniczy Człowiek

Leonid Khachiyan, rosyjski matematyk i profesor na Rutgers University, który w 1979 roku opublikował przełomowe twierdzenie, które pomogło rozwinąć dziedzinę programowania liniowego, zmarł 29 kwietnia w wieku 52 lat.

Przełom Khachiyana, polegający na zastosowaniu podejścia znanego jako metoda elipsoidy do programowania liniowego, nadal pomaga informatykom w ich wysiłkach, aby stawić czoła niezwykle złożonym wyzwaniom związanym z planowaniem i alokacją zasobów w dziedzinach od finansów po telekomunikację po przemysł lotniczy.

Ta historia była częścią naszego wydania z września 2005 r.

• Zobacz resztę numeru
• Subskrybuj

Kiedy Khachiyan po raz pierwszy opublikował swoją pracę o metodzie elipsoidy, był mało znanym 27-letnim matematykiem studiującym matematykę obliczeniową w Centrum Obliczeniowym Radzieckiej Akademii Nauk w Moskwie. Chociaż opublikował swoje odkrycia w: Doklady Akademii Nauk , szanowane czasopismo akademii, dopiero kilka miesięcy później dwóch amerykańskich naukowców przedstawiło swój sucho zatytułowany artykuł – Algorytm wielomianowy w programowaniu liniowym – szerszemu gronu informatyków i matematyków teoretycznych. Po ogłoszeniu ustaleń w Nauka w 1979 roku Khachiyan został gwiazdą informatyki.

Nowy Jork Czasy , który przedstawił osiągnięcia Chaczijana w artykule z listopada 1979 r. zatytułowanym Soviet Mathematician Is Obscure No More, nazwał go tajemniczym autorem nowego twierdzenia matematycznego, które wstrząsnęło światem analizy komputerowej. Biorąc pod uwagę napięcia w epoce zimnej wojny, wynik Chaczijana wywołał zarówno podekscytowanie, jak i zaniepokojenie, wspomina Michael Grigoriadis, kolega Khachiyana z Rutgers, który w 1979 roku pracował dla IBM. Ale znaczenie jego przełomu nie umknęło nikomu w środowisku akademickim i przemysłowym. Grigoriadis przypomina sobie, że usłyszał, że dyrektor generalny IBM poprosił swoje grupy badawcze o ocenę odkrycia, o którym informowała prasa.

Programowanie liniowe to matematyczne podejście do alokacji zasobów. Pojawił się w latach 40. XX wieku, gdy wojsko amerykańskie walczyło o rozwiązanie złożonych problemów planowania wojennego. George Dantzig, absolwent matematyki w czasie II wojny światowej, który został powołany przez Siły Powietrzne Stanów Zjednoczonych do pomocy w logistyce, położył podwaliny pod programowanie liniowe i wprowadził swoją metodę simpleks w 1947 roku. Algorytm simpleks zapewnił praktyczne podejście do określania, w jaki sposób skończoną liczbę zasobów można by przydzielić w najbardziej efektywny sposób i jest ona wykorzystywana do dziś.

Metoda elipsoidalna Chaczijana, będąca poważnym odejściem od dominującego myślenia tamtych czasów, odpowiadała na otwarte pytanie o złożoność programowania liniowego i zachęcała do nowych kierunków badań, powiedział Grigoriadis. Khachiyan znacząco przyczynił się do optymalizacji kombinatorycznej, której zastosowania obejmują wydajne trasowanie pakietów danych przez Internet w celu zmniejszenia ogólnych opóźnień i zarządzanie złożonymi trasami transportu ciężarowego.

Po uzyskaniu referencji akademickich w 1979 r. Chaczijan spędził następną dekadę w Rosji, piastując szereg stanowisk w Centrum Obliczeniowym oraz w Moskiewskim Instytucie Fizyki i Technologii. Khachiyan w końcu przybył do Stanów Zjednoczonych w 1989 r. na wizytę w Szkole Badań Operacyjnych i Inżynierii Przemysłowej Uniwersytetu Cornell. Następnie zaproponowano mu spotkanie w Wydziale Informatyki Rutgers, gdzie ostatecznie uzyskał posadę w 1992 roku. Khachiyan został naturalizowanym obywatelem USA w 2000 roku.

ukryć