Intelligent Machines

Obituary: Mystery Man

An obscure Russian mathematician named Leonid Khachiyan changed how we allocate resources.

Leonid Khachiyan, a Russian mathematician and a professor at Rutgers University who published a groundbreaking theorem in 1979 that helped advance the field of linear programming, died April 29 at the age of 52.

Khachiyan’s breakthrough, applying an approach known as the ellipsoid method to linear programming, continues to aid computer scientists in their efforts to tackle the enormously complex challenges of scheduling and resource allocation in fields ranging from finance to telecommunications to the airline industry.

When Khachiyan first published his work on the ellipsoid method, he was a little-known 27-year-old mathematician studying computational mathematics at the Computing Center of the Soviet Academy of Sciences in Moscow. Though he published his findings in Doklady Akademii Nauk, the academy’s well-respected journal, it wasn’t until months later that two U.S.-based academics introduced his dryly entitled paper – “A Polynomial Algorithm in Linear Programming” – to a broader audience of computer scientists and theoretical mathematicians. After the findings were reported in Science in 1979, Khachiyan became a computer science celebrity.

This story is part of our September 2005 Issue
See the rest of the issue
Subscribe

The New York Times, which profiled Khachiyan’s achievement in a November 1979 article entitled “Soviet Mathematician Is Obscure No More,” called him “the mystery author of a new mathematical theorem that has rocked the world of computer analysis.” Given the tensions of the Cold War era, Khachiyan’s result prompted both excitement and alarm, recalls Michael Grigoriadis, a colleague of Khachiyan’s at Rutgers, who was working for IBM in 1979. But the importance of his breakthrough escaped nobody in academia and industry. Grigoriadis recalls hearing that IBM’s CEO asked his research groups to assess the discovery reported in the press.

Linear programming is a mathematical approach to resource allocation. It emerged in the 1940s, as the U.S. military struggled to address complex issues of wartime planning. George Dantzig, a graduate student in mathematics during World War II who was enlisted by the U.S. Air Force to help with logistics, laid the foundation for linear programming and introduced his “simplex method” in 1947. The simplex algorithm provided a practical approach to determining how a finite number of resources could be allocated in the most efficient way, and it is still used today.

A major departure from the prevailing thinking of that era, Khachiyan’s ellipsoid method answered the open question about the complexity of linear programming and encouraged new avenues of research, said Grigoriadis. Khachiyan contributed significantly to the field of combinatorial optimization, whose applications include the efficient routing of data packets across the Internet to reduce overall delay and the management of complex trucking routes.

After establishing his academic credentials in 1979, Khachiyan spent the next decade in Russia, holding a series of positions at the Computing Center and at the Moscow Institute of Physics and Technology. Khachiyan finally came to the United States in 1989 for a visiting appointment at Cornell University’s School of Operations Research and Industrial Engineering. He was then offered an appointment at the Rutgers Department of Computer Science, where he ultimately gained tenure in 1992. Khachiyan became a naturalized U.S. citizen in 2000.

Tech Obsessive?
Become an Insider to get the story behind the story — and before anyone else.
Subscribe today

Uh oh–you've read all five of your free articles for this month.

Insider Premium

$179.95/yr US PRICE

More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe and become an Insider.

  • Insider Premium {! insider.prices.premium !}*

    {! insider.display.menuOptionsLabel !}

    Our award winning magazine, unlimited access to our story archive, special discounts to MIT Technology Review Events, and exclusive content.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

    First Look. Exclusive early access to stories.

    Insider Conversations. Join in and ask questions as our editors talk to innovators from around the world.

  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus ad-free web experience, select discounts to partner offerings and MIT Technology Review events

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning magazine and daily delivery of The Download, our newsletter of what’s important in technology and innovation.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

You've read of free articles this month.