Clifford S. Stein | Estimating Solutions to Difficult Problems

Clifford S. Stein
Professor of Industrial Engineering and Operations Research and of Computer Science
This profile is included in the publication Excellentia, which features current research of Columbia Engineering faculty members.
                               Photo by Eileen Barroso

Cliff Stein has built a career on finding algorithms to solve difficult problems—but not precisely. Stein specializes in algorithms that estimate the answer to problems that are difficult to solve. In operations research and computer science, these are problems that grow exponentially more complex as the number of inputs grows.

This contrasts with simple problems, like alphabetizing words. Double the number of inputs—words—and it takes only about twice as long to accomplish the task.

A well-known difficult problem is calculating the most efficient route for a salesman to visit different cities. To find the most efficient route, a computer must calculate all possible outcomes. For five cities, there are 120 potential paths. For 10 cities, 3.6 million.

“For 80 cities, there are roughly as many possible answers as there are atoms in the universe,” Stein said.

“No conceivable advance in computing power would enable us to solve that problem precisely,” Stein noted. “But if you’re willing to solve it approximately, you can do so more easily and efficiently.”

Many algorithms already exist for estimating the solution for the traveling salesman and other difficult problems. Stein prefers to break new ground, studying the fundamental structure of problems to develop new algorithms.

“There’s a collection of algorithmic tools that are commonly used to solve many problems,” he said. “But often there are problems that are important to solve. It is worth investing the time to study their mathematical or combinatorial structure to come up with a solution specific to that problem.”

Much of his work deals with scheduling everything from computer systems to factories. Scheduling starts with jobs and the machines needed to complete them. Constraints—jobs take different amounts of time, some are more important than others, some tasks depend on others—add to the difficulty. So do different objectives, like fast completion, minimal resources, and rapid response.

Stein is looking at ways to apply scheduling to computer processors in order to save energy. “Most chips can run at four or five different speeds,” he said. “If you run at half speed, you decrease energy use by roughly a factor of four. But no one has figured out how to give chips the intelligence to know when to slow down, so they typically run at top speed all the time.”

By estimating a chip’s workload, constraints, and performance goals, Stein believes he can achieve significant energy savings. Even if his estimates are not precise.

B.S.E., Princeton, 1987; M.S., Massachusetts Institute of Technology, 1989; Ph.D., MIT, 1992

500 W. 120th St., Mudd 510, New York, NY 10027    212-854-2993