Real-life problems realistically solved

When you want to tackle a problem that would require a disproportionate amount of time and effort to solve exactly, you can use an approximation algorithm, says Piotr Sankowski of the University of Warsaw. The result may not be as precise as the outcome of an exact calculation, but it will be very close — and, depending on what you need it for, there may be little point in getting bogged down in details.
Sankowski has benefited from an ERC Starting Grant for the PAAL project, which produced a library of such algorithms. Together with his team, he designed these approximation programmes to be generic: they don’t just work for individual examples of particular types of problems, but can be adapted to address other questions of a similar nature.
“Our library is easy to install, to use and to modify,” Sankowski notes. “It is based on templates that you can adapt for different use cases.”

Adaptable algorithms
As an example of a conundrum best addressed through approximation, Sankowski points to the notorious Travelling Salesman Problem — the challenge of working out the shortest possible route for a sales rep who wants to visit several cities and then return home. Doable with paper, pen and patience if there are very few cities to consider, no doubt, but as the list grows longer, so does the number of possible permutations, and thus the difficulty of the task.
Of course, using a computer, it is possible to work out the optimal sequence even for large numbers of cities. In theory, it would also be possible to cover additional criteria, such as preferences for different types of transport. But by the time a programme written for this purpose would deliver a conclusive answer, the salesman’s travelling days may well be over.
Does it matter? In fact, it does. This type of problem arises in areas as varied as transport and manufacturing, e.g., with regard to routing vehicles or drilling holes into circuit boards. Timely, efficient solutions can help businesses to save time and money, and approximation algorithms can help to produce them.

A fresh approach to approximation
Sankowski intends to tap this potential in a new enterprising venture following the imminent end of PAAL. The follow-on project, named PAAL-POC, will develop e-commerce support services based on this library, with the eventual aim of setting up a spin-off company.
“Approximation algorithms can be used to model trade or customer behaviour. We will work on this aspect with a number of companies involved in e-commerce,” Sankowski explains. “The aim is to predict how the market is likely to react when a company introduces changes — in its business strategy, for example.”
Prospective clients of the future spin-off will benefit from another specificity of the algorithms developed in PAAL: their ability to factor in both random and regular structures. Social networks, for example, grow partly along existing lines of interaction and partly through spontaneous new connections, Sankowski explains. Such interplay between average case and worst-case scenarios is relevant to many mechanisms at play in e-business, he notes.  
PAAL was backed by an ERC Starting Grant, a type of funding which the European Research Council awards to outstanding research proposals submitted by young researchers with a promising scientific track record. PAAL-POC also benefits from ERC support, attributed in this case through the Proof of Concept scheme. This programme encourages beneficiaries of earlier ERC grants to explore the commercial or innovation potential of their findings.
The grants have advanced Sankowski’s career in a number of ways, he reports. They have helped to establish him as an independent team leader within his university, he notes, and they have also raised his visibility at international level.
The establishment of a spin-off should give his career a further boost. Once this is new venture is up and running, he intends to return to his research. Clearly, algorithms and approximation hold endless fascination.