Word: karmarkar
(lookup in dictionary)
(lookup stats)
Dates: during 1984-1984
Sort By: most recent first
(reverse)
...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...
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...
...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...
...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...
| 1 |