OK Computer: a world of algorithms

Using an Internet search engine to find the hottest restaurant in town? Letting your car’s GPS tell you where to turn left to reach the parking garage? Worrying if your money is safe when you use online banking? Looking for the love of your life on an Internet dating site? You can be sure that an algorithm has helped you on your way.

No easy answers

Not that such mundane questions as restaurant choice or people’s love lives are part of the day-to-day work of the Algorithms Research Group at the University of Bergen (UiB). Yet their work to develop new mathematical theories to find and provide better algorithms will most certainly be of help to each and every one of us in our daily lives.

“In the algorithms group we work on problems deemed ‘difficult’,” says Professor Pinar Heggernes. “There are problems for which there are still no good algorithms. Problems it would take a computer thousands of years to solve.”

However, the group does not primarily deal with practical issues. They are mainly focusing on the mathematical representation of a problem.

“Everyone in our field of research dreams of solving complex problems, because there are huge practical consequences if you do. For instance, the security systems used in Internet banking are based on problems of this kind, whose difficulty level is unresolved. If someone comes up with a simple and efficient algorithm for one of these problems, then all online banking security evaporates,” Heggernes explains. “On the other hand, however, a range of complex tasks will suddenly become possible to solve fast and efficiently.”

On Saturday 5 October you can be certain to find a number of members of the Algorithms Research Group competing for glory at the Nordic Collegiate Programming Contest.

Searching for ‘good’ algorithms

Professor Fedor Fomin of the same group is the recipient of an advanced grant from the European Research Council (ERC), one of six such grant recipients at UiB. So what does it take to be awarded an ERC grant?

“A lot of work and a bit of luck,” Fomin says and smiles.

The ERC grant awarded to Professor Fomin focuses on special types of algorithms called pre-processing algorithms. While usually algorithms try to solve the problem, the goal of pre-processing algorithms is more humble; they just try to simplify the problem. Combined with other algorithms, pre-processing can be very powerful.

He uses Sudoku puzzles as an example.

“A naïve strategy to solve the puzzle would be to use ‘brute force’ by trying all possibilities of filling the empty cells. But there are so many variants that this approach can take months if not ages! Instead of trying brute force immediately, an experienced Sudoku-solver tries to simplify the puzzle by eliminating the impossible cases. In other words, doing pre-processing,” Fomin explains. “There are many rules in Sudoku allowing the solution of most easy puzzles. For more difficult puzzles such pre-processing is used to reduce possible cases, and with a combination of other techniques, to solve the puzzle.”

“The goal of the project is to understand pre-processing algorithms theoretically,” he continues. “We want to know why and when such algorithms behave well and why and when they fail. Pre-processing algorithms are ubiquitous and we need this theory to find out how they can be improved.”

So why do algorithms matter?

“Algorithms are high-level descriptions of instructions to perform computational tasks. They form the basis of the computer and computational science. For engineers and experimentalists, an algorithm is a success if it works well in practice,” Fomin says. “Design and analysis of algorithms is also one of the most important areas in theory of computing, and the goal here is to provide provable guarantees about the performance of algorithms under all conditions. Developing rigorous mathematical theories that explain the behaviour of practical algorithms has become an increasingly important challenge, and this is the topic of my project.”

Speed is essential

Algorithms are put together in different ways and speed is of the essence. But speed or no speed, there are a number of issues that look surmountable at the outset, but that may turn out to be impossible to solve in real life.

“Say there is a gathering of 1,000 people and amongst them you want to select the largest possible group of people who all know one another. That is an example of one such difficult question,” Heggernes points out. “It is easy to ask all of them who they know. And it is easy to pick a group at random to and check if they know each other. But to pick the largest group who all know one another, the only algorithm we have is basically to run through all possible selections of groups of people from the gathering. That, however, takes an unbelievably huge amount of time.”

Another example would be the destination map of an airline. Scheduling aircraft and crew is a classic problem for which good algorithms come in handy. On the one hand an airline may want to maximise its profit by purchasing as few planes as necessary and thus employ as few pilots as possible. They may also wish to plan flights so that planes always have a high seat load. It doesn’t take many destinations before such a problem becomes extremely time-consuming to solve.

Brains over computers

It may sound rather ironic that computers do not play a major part in algorithms research. Fomin, Heggernes and the other algorithms researchers at UiB spend most of their time thinking, writing, and reading articles about other people’s results. Nothing works better than thinking alongside others.

“Guests visit us frequently. Talented people arrive here to work with us for a week or two. Discussions are an integral part of what we do, and it is way easier to do this face-to-face than via e-mail,” says Heggernes.

Yet in a time where the amount of data is exploding beyond calculating power and all information is stored and registered, there is ever greater need for good algorithms: not only to retrieve information from the data, but also to store the material in a way that makes it more accessible.

Even though the algorithm researchers work on mathematical models, they always keep in mind that their work needs a practical outlet. Getting excited about a nice mathematical result is easy, but if it has no use beyond itself, this result will soon gather dust in a drawer and be forgotten.

“At the end of the day the implications of our results should be usable in a computer programme. We may define problems that give difficult theoretical results and better mathematical understanding, but this is only of use if the theory helps us understand some practical behaviour as well,” says Heggernes.

(Translation: Sverre Ole Drønen.)

This article was first published in UiB’s magazine Hubro international 2013/2014.