Doodsbrief: Mystery Man

Leonid Khachiyan, een Russische wiskundige en professor aan de Rutgers University die in 1979 een baanbrekende stelling publiceerde die het veld van lineaire programmering vooruit hielp, stierf op 29 april op 52-jarige leeftijd.

De doorbraak van Khachiyan, die een benadering toepast die bekend staat als de ellipsoïde methode voor lineair programmeren, blijft computerwetenschappers helpen bij hun inspanningen om de enorm complexe uitdagingen van planning en toewijzing van middelen aan te pakken op gebieden variërend van financiën tot telecommunicatie tot de luchtvaartindustrie.

Dit verhaal maakte deel uit van ons nummer van september 2005

• Zie de rest van het probleem
• Abonneren

Toen Khachiyan zijn werk over de ellipsoïde methode voor het eerst publiceerde, was hij een weinig bekende 27-jarige wiskundige die computationele wiskunde studeerde aan het rekencentrum van de Sovjet Academie van Wetenschappen in Moskou. Hoewel hij zijn bevindingen publiceerde in Doklady Akademii Nauk , het gerespecteerde tijdschrift van de academie, introduceerden twee in de VS gevestigde academici pas maanden later zijn droog getitelde paper - A Polynomial Algorithm in Linear Programming - aan een breder publiek van computerwetenschappers en theoretische wiskundigen. Nadat de bevindingen werden gerapporteerd in Wetenschap in 1979 werd Khachiyan een beroemdheid in de computerwetenschappen.

de New York Keer , waarin Khachiyans prestatie werd geprofileerd in een artikel van november 1979 getiteld Soviet Mathematician Is Obscure No More, noemde hem de mysterieauteur van een nieuwe wiskundige stelling die de wereld van computeranalyse op zijn kop heeft gezet. Gezien de spanningen van het tijdperk van de Koude Oorlog, veroorzaakte het resultaat van Khachiyan zowel opwinding als alarm, herinnert Michael Grigoriadis zich, een collega van Khachiyan bij Rutgers, die in 1979 voor IBM werkte. Maar het belang van zijn doorbraak ontging niemand in de academische wereld en de industrie. Grigoriadis herinnert zich dat hij hoorde dat de CEO van IBM zijn onderzoeksgroepen vroeg om de ontdekking die in de pers werd gemeld, te beoordelen.

Lineair programmeren is een wiskundige benadering van de toewijzing van middelen. Het ontstond in de jaren 1940, toen het Amerikaanse leger worstelde om complexe problemen van oorlogsplanning aan te pakken. George Dantzig, een afgestudeerde wiskundestudent tijdens de Tweede Wereldoorlog die door de Amerikaanse luchtmacht werd ingeschakeld om te helpen met logistiek, legde de basis voor lineair programmeren en introduceerde zijn simplex-methode in 1947. Het simplex-algoritme bood een praktische benadering om te bepalen hoe een een eindig aantal middelen zou op de meest efficiënte manier kunnen worden toegewezen, en het wordt nog steeds gebruikt.

Een belangrijke afwijking van het heersende denken van die tijd, de ellipsoïde methode van Khachiyan beantwoordde de open vraag over de complexiteit van lineaire programmering en moedigde nieuwe onderzoeksrichtingen aan, zei Grigoriadis. Khachiyan heeft een belangrijke bijdrage geleverd op het gebied van combinatorische optimalisatie, waarvan de toepassingen de efficiënte routering van datapakketten via internet omvatten om de algehele vertraging te verminderen en het beheer van complexe vrachtwagenroutes.

Nadat hij in 1979 zijn academische kwalificaties had behaald, bracht Khachiyan het volgende decennium door in Rusland, waar hij een aantal functies bekleedde bij het Computing Center en bij het Moskouse Instituut voor Fysica en Technologie. Khachiyan kwam uiteindelijk in 1989 naar de Verenigde Staten voor een bezoek aan de Cornell University's School of Operations Research and Industrial Engineering. Vervolgens kreeg hij een aanstelling aangeboden bij het Rutgers Department of Computer Science, waar hij uiteindelijk in 1992 een vaste aanstelling kreeg. Khachiyan werd in 2000 genaturaliseerd tot Amerikaans staatsburger.

zich verstoppen