Navigation path

Countries
Countries
  Algeria
  Argentina
  Australia
  Austria
  Bangladesh
  Belarus
  Belgium
  Benin
  Bolivia
  Botswana
  Brazil
  Bulgaria
  Burkina Faso
  Cameroon
  Canada
  Cape Verde
  Chile
  China
  Colombia
  Costa Rica
  Croatia
  Cyprus
  Czech Republic
  Denmark
  Ecuador
  Egypt
  Estonia
  Ethiopia
  Finland
  France
  Gambia
  Georgia
  Germany
  Ghana
  Greece

Countries
Countries
  Algeria
  Argentina
  Australia
  Austria
  Bangladesh
  Belarus
  Belgium
  Benin
  Bolivia
  Botswana
  Brazil
  Bulgaria
  Burkina Faso
  Cameroon
  Canada
  Cape Verde
  Chile
  China
  Colombia
  Costa Rica
  Croatia
  Cyprus
  Czech Republic
  Denmark
  Ecuador
  Egypt
  Estonia
  Ethiopia
  Finland
  France
  Gambia
  Georgia
  Germany
  Ghana
  Greece


   Infocentre

Published: 22 January 2016  
Related theme(s) and subtheme(s)
Frontier research (ERC)
Information society
Research policySeventh Framework Programme
Countries involved in the project described in the article
Italy  |  Poland
Add to PDF "basket"

Real-life problems realistically solved

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.

Programming code

© maciek905 - Fotolia.com

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.

Read more:

Project details

  • Project acronym: PAAL
  • Participants: Poland (Coordinator), Italy
  • Project reference: 259515
  • Total cost: € 1 000 000
  • EU contribution: € 1 000 000
  • Duration: November 2010 - October 2015

Convert article(s) to PDF

No article selected


loading


Search articles

Notes:
To restrict search results to articles in the Information Centre, i.e. this site, use this search box rather than the one at the top of the page.

After searching, you can expand the results to include the whole Research and Innovation web site, or another section of it, or all Europa, afterwards without searching again.

Please note that new content may take a few days to be indexed by the search engine and therefore to appear in the results.

Print Version
Share this article
See also
Project Website
Project information on CORDIS






  Top   Research Information Center
 
Countries
Countries
  Algeria
  Argentina
  Australia
  Austria
  Bangladesh
  Belarus
  Belgium
  Benin
  Bolivia
  Botswana
  Brazil
  Bulgaria
  Burkina Faso
  Cameroon
  Canada
  Cape Verde
  Chile
  China
  Colombia
  Costa Rica
  Croatia
  Cyprus
  Czech Republic
  Denmark
  Ecuador
  Egypt
  Estonia
  Ethiopia
  Finland
  France
  Gambia
  Georgia
  Germany
  Ghana
  Greece

Countries
Countries
  Algeria
  Argentina
  Australia
  Austria
  Bangladesh
  Belarus
  Belgium
  Benin
  Bolivia
  Botswana
  Brazil
  Bulgaria
  Burkina Faso
  Cameroon
  Canada
  Cape Verde
  Chile
  China
  Colombia
  Costa Rica
  Croatia
  Cyprus
  Czech Republic
  Denmark
  Ecuador
  Egypt
  Estonia
  Ethiopia
  Finland
  France
  Gambia
  Georgia
  Germany
  Ghana
  Greece