Folding the Perfect Corner

By Natalie Angier

A young Bell scientist makes a major math breakthrough

Every day 1,200 American Airlines jets crisscross the U.S., Mexico, Canada and the Caribbean, stopping in 110 cities and bearing over 80,000 passengers. More than 4,000 pilots, copilots, flight personnel, maintenance workers and baggage carriers are shuffled among the flights; a total of 3.6 million gal. of high-octane fuel is burned. Nuts, bolts, altimeters, landing gears and the like must be checked at each destination. And while performing these scheduling gymnastics, the company must keep a close eye on costs, projected revenue and profits.

Like American Airlines, thousands of companies must routinely untangle the myriad variables that complicate the efficient distribution of their resources. Solving such monstrous problems requires the use of an abstruse branch of mathematics known as linear programming. It is the kind of math that has frustrated theoreticians for years, and even the fastest and most powerful computers have had great difficulty juggling the bits and pieces of data. Now Narendra Karmarkar, a 28-year-old Indian-born mathematician at Bell Laboratories in Murray Hill, N.J., after only a year's work has cracked the puzzle of linear programming by devising a new algorithm, a step-by-step mathematical formula. He has translated the procedure into a program that should allow computers to track a greater combination of tasks than ever before and in a fraction of the time.

Unlike most advances in theoretical mathematics, Karmarkar's work will have an immediate and major impact on the real world. "Breakthrough is one of the most abused words in science," says Ronald Graham, director of mathematical sciences at Bell Labs. "But this is one situation where it is truly appropriate."

Before the Karmarkar method, linear equations could be solved only in a cumbersome fashion, ironically known as the simplex method, devised by Mathematician George Dantzig in 1947. Problems are conceived of as giant geodesic domes with thousands of sides. Each corner of a facet on the dome represents a possible solution to the equation. Using the simplex method, the computer scours the surface of the dome millions of times to pinpoint the corner with the most likely solution. But the method is slow, and it works only when there are merely a few thousand variables to sort through. Says Karmarkar: "Once you get above 15,000 or 20,000 variables, the method sort of runs out of steam."

Karmarkar's technique does not attempt to calculate the location of every solution but takes a circuitous route, eliminating groups of combinations without actually considering them, all the time changing the shape of the dome. The mathematician compares this search to origami, the Japanese art of paper folding: the pieces of paper are creased and shaped until the perfect corner -- the long-sought solution -- is in the center of the figure.

When the computer program be comes available to commercial users, American Airlines will be far from the only customer waiting in line. Bell Labs' parent company, AT&T, will probably employ the algorithm to route millions of telephone calls through hundreds of thousands of cities and towns more efficiently and profitably. Exxon has expressed interest in Karmarkar's program to help improve its allocation of supplies of crude oil among various refineries. For many large companies, says Graham, finding the best solution, as opposed to one that is merely workable, "can mean the difference between a good balance sheet and a mediocre one."

-- By Natalie Angier. Reported by Peter Stoler/New York

With reporting by Peter Stoler