Finding the optimal solutions to complex problems can be dramatically faster
A new algorithm could dramatically slash the time it can take computers to recommend movies or route taxis.
The new algorithm, developed by Harvard University researchers, solves optimization problems exponentially faster than previous algorithms by cutting the number of steps required. Surprisingly, this approach works “without sacrificing the quality of the resulting solution,” says study senior author Yaron Singer, at Harvard University.
Optimization problems seek to find the best answer from all possible solutions, such as mapping the fastest route from point A to point B. Many algorithms designed to solve optimization problems have not changed since they were first described in the 1970s.
Previous optimization algorithms generally worked in a step-by-step process, with the number of steps proportional to the amount of the data analyzed. For example, a movie-recommendation algorithm might sequentially look at every film similar to one a person liked.
However, previous optimization algorithms had a diminishing-returns property: As they progressed, the relative gain from each step became smaller and smaller. This meant that for optimization problems involving vast amounts of data, finding the best solutions could prove extraordinarily computationally expensive.
Read more: New Optimization Algorithm Exponentially Speeds Computation