Sankowski: Sometimes it's better to look for good solutions rather than ideal ones

Dr. Piotr Sankowski of the Faculty of Mathematics, Computer Science and Mechanics of the University of Warsaw focuses on approximation algorithms that are very useful in the optimisation of processes, for example in logistics and e-commerce. For his project in 2010 he received a prestigious Starting Grant from the European Research Council (ERC). Now the project is coming to an end, but Sankowski wants to continue his research and commercialise it. This will be possible with another grant, Proof of Concept, which he received from the ERC in July.

Some of the problems Piotr Sankowski investigates may seem trivial: you have to pack up smaller parcels into larger parcels to use less cardboard. If there are only a few items for packing, the problem is simple. But when the number of parcels for packing and shipment grows and counts in thousands or even hundreds of thousands, and time is limited, it is not worth it to look for ideal answers - it would take too long and not bring noticeable benefits. In such situations it is better to rely on an approximation algorithm, which will quickly find a solution that might not be perfect, but will be good enough. "For me creating such algorithms is as pleasant solving sudoku is for others. My research is my hobby" - admitted Sankowski.

The researcher and his team create an open library, where you can already find approx. 30 various approximation algorithms. "Each of these apps is designed so that it can easily be used in different ways to solve various problems" - noted Sankowski. He added that algorithms are available in open access, and developers can easily modify them to fit their needs. This is an unusual approach; typically algorithms of this type are written specifically for a particular problem, so they cannot be reused for another task.

Sankowski’s algorithms include, for example, a program that may be useful in solving the classic travelling salesman problem that vexes many logistics companies. The problem concerns visiting a number of specific cities in the shortest possible time. The question is, in what order should the cities be visited. Logistics companies could easily adapt Sankowski’s solution for their needs.

Approximation algorithms can be applied in many different areas of life, for example for cutting glass. "Glassworks manufacture huge panes of glass, and they need to be cut to specific pieces to minimise the waste. Glass-cutting companies must deal with such problems on a daily basis" - admitted the researcher and emphasised that adequate algorithms can improve this process.

Sankowski added, however, that approximation algorithms are most commonly used in e-commerce, online trade. He gave an example: "When you go to a large website, ads are displayed. But it is not one ad shown to all users all day" - said the computer scientist. He explained that when an internet user enters the website, there is an internet auction that takes fractions of a second. Advertisers bid to buy the ad displayed to this particular user. The company that offers more, wins. "It happens for each user. It is hard to imagine a person sending all these offers. Programs do that. Optimising the company\'s participation in an auction is a common problem, for which approximation algorithms are used. They allow to calculate how much advertising should be worth so that it costs the least, but reaches as many potential customers as possible" - he noted.

The scientist added that the algorithms he is working on will also be useful in online stores. "If a customer buys two products, it is worth it to suggest a third product he might be interested in. Algorithms help choose the best product for each customer" - he says. No need to employ a psychologist to analyse the behaviour of each client. It is better to use statistics. The key is to model specific customer groups and sort the products the store offers.

Library of Sankowski’s solutions is available to all users, and already uses for free by developers from around the world. Now Sankowski wants to also start a company which would offer solutions to more specific problems. "If you have an optimisation problem, we will try to help you" - said the researcher. He announced that for the time being the offer will be addressed to companies in Poland, but he hopes that with time the company will expand an offer services to customers from abroad.

PAP - Science and Scholarship in Poland, Ludwika Tomala

lt/ agt/ mrt/

tr. RL