Dödsannons: Mystery Man

Leonid Khachiyan, en rysk matematiker och professor vid Rutgers University som publicerade ett banbrytande teorem 1979 som hjälpte till att utveckla området linjär programmering, dog den 29 april vid 52 års ålder.

Khachiyans genombrott, genom att tillämpa en metod som kallas ellipsoidmetoden för linjär programmering, fortsätter att hjälpa datavetare i deras ansträngningar att ta itu med de enormt komplexa utmaningarna med schemaläggning och resursallokering inom områden som sträcker sig från finans till telekommunikation till flygindustrin.

Den här historien var en del av vårt septembernummer 2005

• Se resten av frågan
• Prenumerera

När Khachiyan först publicerade sitt arbete om ellipsoidmetoden, var han en föga känd 27-årig matematiker som studerade beräkningsmatematik vid Computing Center vid den sovjetiska vetenskapsakademin i Moskva. Även om han publicerade sina fynd i Doklady Akademii Nauk , akademins välrespekterade tidskrift, var det inte förrän månader senare som två USA-baserade akademiker introducerade hans torrt berättigade uppsats – A Polynomial Algorithm in Linear Programming – för en bredare publik av datavetare och teoretiska matematiker. Efter att fynden rapporterats i Vetenskap 1979 blev Khachiyan en datavetenskaplig kändis.

New York Tider , som profilerade Khachiyans prestation i en artikel från november 1979 med titeln Soviet Mathematician Is Obscure No More, kallade honom den mystiska författaren till ett nytt matematiskt teorem som har skakat världen av datoranalys. Med tanke på det kalla krigets spänningar väckte Khachiyans resultat både spänning och oro, minns Michael Grigoriadis, en kollega till Khachiyans på Rutgers, som arbetade för IBM 1979. Men vikten av hans genombrott undgick ingen i akademin och industrin. Grigoriadis minns att han hörde att IBM:s VD bad sina forskargrupper att bedöma upptäckten som rapporterats i pressen.

Linjär programmering är en matematisk metod för resursallokering. Det dök upp på 1940-talet, när den amerikanska militären kämpade för att ta itu med komplexa frågor om krigstidsplanering. George Dantzig, en doktorand i matematik under andra världskriget som togs in av det amerikanska flygvapnet för att hjälpa till med logistik, lade grunden för linjär programmering och introducerade sin simplexmetod 1947. Simplexalgoritmen gav ett praktiskt tillvägagångssätt för att bestämma hur en ändligt antal resurser skulle kunna fördelas på det mest effektiva sättet, och det används fortfarande idag.

En stor avvikelse från det rådande tänkandet från den eran, besvarade Khachiyans ellipsoidmetod den öppna frågan om komplexiteten i linjär programmering och uppmuntrade nya forskningsvägar, sa Grigoriadis. Khachiyan bidrog avsevärt till området kombinatorisk optimering, vars tillämpningar inkluderar effektiv dirigering av datapaket över Internet för att minska totala förseningar och hantering av komplexa lastbilsrutter.

Efter att ha etablerat sina akademiska meriter 1979 tillbringade Khachiyan nästa decennium i Ryssland och innehade en rad positioner vid Computing Center och vid Moskvainstitutet för fysik och teknik. Khachiyan kom slutligen till USA 1989 för en besöksutnämning vid Cornell Universitys School of Operations Research and Industrial Engineering. Han erbjöds sedan en tid vid Rutgers Department of Computer Science, där han slutligen fick tjänstgöring 1992. Khachiyan blev en naturaliserad amerikansk medborgare 2000.

Dölj