Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo

 

Unsupported browser: Your browser does not meet modern web standards. See how it scores »

{ action.text }

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.

0 comments about this story. Start the discussion »

Tagged: Computing

Reprints and Permissions | Send feedback to the editor

From the Archives

Close

Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me