In life, we sometimes have to make decisions without all the information we want; that’s true in computer science, too. This is the realm of online algorithms — which, despite their name, don’t necessarily involve the internet. Instead, these are problem-solving strategies that respond to data as it arrives, without any knowledge of what might come next. That ability to cope with uncertainty makes these algorithms useful for real-world conundrums, like managing memory on a laptop or choosing which ads to display to people who browse the web.
Researchers study generalized versions of these problems to investigate new methods for tackling them. Among the most famous is the “k-server problem,” which describes the thorny task of dispatching a fleet of agents to fulfill requests coming in one by one. They could be repair technicians or firefighters or even roving ice cream salespeople.
“It’s really simple to define this problem,” said Marcin Bieńkowski, an algorithms researcher at the University of Wrocław in Poland. But it “turns out to be bizarrely difficult.” Since researchers began attacking the k-server problem in the late 1980s, they have wondered exactly how well online algorithms can handle the task.
Over the decades, researchers began to believe there’s a certain level of algorithmic performance you can always achieve for the k-server problem. So no matter what version of the problem you’re dealing with, there’ll be an algorithm that reaches this goal. But in a paper first published online last November, three computer scientists showed that this isn’t always achievable. In some cases, every algorithm falls short.
“I am happy to say that it was a big surprise to me,” said Anupam Gupta, who studies algorithms at Carnegie Mellon University and was not involved in the paper. The work offers “deeper insight into the central problem in this area.”
Computer scientists first outlined this problem in 1988. To get a sense of it, let’s imagine a company that employs plumbers. As calls come in, the company needs to decide which plumber goes to which location. The company’s goal — and the goal of an algorithm for the k-server problem — is to minimize the total distance traveled by all the plumbers.
The tricky part is that the company doesn’t know in advance where the calls will come from. If it did, then it could rely on an “offline algorithm” that knows the future. In particular, it could use an ideal dispatching strategy that finds a solution with the least total travel for any string of calls. No online algorithm can ever beat it, or even reliably match it.
But researchers want to get as close as possible. They measure an online algorithm’s performance by comparing the travel distance in each strategy, calculating what’s known as the competitive ratio. Algorithm designers try to craft online strategies that approach the offline ideal, whittling this ratio down toward 1.
