Real-life problems realistically solved

Friday, 22 January, 2016
Is a precise answer always better than a slightly less detailed one? Not necessarily. Some problems could take forever to compute and tie up vast IT capacity. Where solutions are needed urgently, e.g. in business or manufacturing, near-enough can be more than enough. ERC-funded research has produced a library of fast, powerful approximation algorithms.

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.

Read more

Prof. Piotr Sankowski

© P. Sankowski

Practical Approximation Algorithms
Project Acronym: