Solving problems by computer just got a lot faster | Science News

SUPPORT SCIENCE NEWS

Science News is a nonprofit.

Help us keep you informed.


News in Brief

Solving problems by computer just got a lot faster

A new algorithm shuffles through all possible solutions to find the best answer

By
7:00am, July 16, 2018
illustration of computer code

SPEED DEMON  This new computer program’s clever number-crunching strategy could route ride shares, discover new drugs and analyze genetic data far faster than other algorithms.

Sponsor Message

A new computer program works smarter, not harder, to solve problems faster than its predecessors.

The algorithm is designed to find the best solution to a given problem among all possible options. Whereas other computer programs winnow down the possibilities one at a time, the new program — presented July 12 at the International Conference on Machine Learning in Stockholm — rules out many choices at once.

For instance, imagine a computer is assigned to compile movie recommendations based on a particular film. The ideal recommendation list would include suggestions that are both similar to the original flick — say, in the same genre — yet different enough from each other to give the viewer a variety of choice. A traditional recommendation system would pore over an entire movie library to find films that best met those criteria and add films to its roster of recommendations one by one, a relatively slow and tedious process.

By contrast, the new program starts by randomly picking a bunch of movies from the library. Among that sample, the system keeps the movies that strike the best balance between relevance to the original film and diversity, and discards the rest. From that smaller pool, the algorithm again chooses films at random and keeps only the best of the bunch. That strategy helps the algorithm build its rec list far faster.

The new algorithm, built by Harvard University computer scientists Yaron Singer and Eric Balkanski, compiled movie suggestions more than 10 times as fast as a standard recommender system. In another trial, it devised optimal routes for cabs in New York City about six times as fast as a conventional automated dispatcher.

This program could also speed up data processing for everything from drug discovery to social media analytics and analyses of genetic data (SN Online: 7/15/15).

Citations

E. Balkanski and Y. Singer. Approximation guarantees for adaptive sampling. International Conference on Machine Learning. Stockholm, July 12, 2018.

Further Reading

E. Conover. Shayan Oveis Gharan finds the shortest route to success. Science News. Vol. 190, October 1, 2016, p. 24.

A. Grant. New algorithm cracks graph problem. Science News. Vol. 188, December 12, 2015, p. 6.

T.H. Saey. Enormous quantities may soon be called ‘genomical.’ Science News Online, July 15, 2015.

T. H. Saey. Big data studies come with replication challengesScience News. Vol. 187, February 7, 2015, p. 22.

Get Science News headlines by e-mail.

More Science & the Public posts

From the Nature Index Paid Content