Photo: Fotolia
From behaviours on dating websites to organ donation systems and organization of work of machinery in a factory - problems, for which science can not find efficient algorithms can be encountered in almost every area of life. Computers would need long years for accurate calculations. But scientists do not give up in their search for the best formulas to simplify the world.
Michał Włodarczyk from the Faculty of Mathematics, Computer Science and Mechanics at the University of Warsaw is working on shortcuts and approximations in calculations that may contribute to progress in informatics. The researcher was awarded by the Foundation for Polish Science in the START stipend program.
There is only one way to properly solved difficult problems. You have to generate all potential solutions and choose the best one. It sounds simple, but it turns out that as we add more elements, the runtime of such programs, mathematical algorithms, grows exponentially. Therefore, it takes computer clusters and long years to perform calculations. After all, each new element must be combined with all the others in every possible solution variant.
Michał Włodarczyk explains what combines various difficult problems at the mathematical level. He wonders if they can be solved in an approximate way, sacrificing accuracy in favour of shortening the algorithm`s runtime. Optimisation problems he analyses belong to the canon of theoretical computer science and their various aspects have been studied for several decades. One example is the distribution of factories.
"Our goal is to open a factory network. We know the location of potential recipients of goods and we have a list of places where a factory can be built, complete with the costs of such an undertaking. Where should we set up factories to minimize the costs of building factories and transporting goods?" - the Foundation for Polish Science stipend holder describes the problem.
The second example is called the Steiner Tree and concerns communication. "There is a given network of connections, e.g. telecommunication. We want to buy the cheapest subset of connections, which will ensure communication between the set of terminals we are interested in. With the help of this problem, you can also model problems concerning the design of integrated circuits and computational biology" - the researcher says.
Another problem is scheduling tasks. There is a set of available machines and you have to plan the execution of multiple tasks in order to minimize the working time. Each machine can perform only one task at a time. Tasks can vary in levels of difficulty and interdependencies.
Another problem concerns designing auctions. Let`s say that you want to sell a collection of goods while following established rules. You cannot withdraw your offer once you have made it. You have partial information on the customers interested in our products and how much they can pay for them. How should you design the auction to maximize profit?
"For many important optimisation problems there are no effective algorithms that can solve the problem accurately. One way to solve this is to use approximation algorithms, find a solution that differs from the optimal one by a certain fixed factor" - the researcher explains.
The difficulty in practical applications is the need to model information about unknown data. An example is investment planning, when you only have simplified predictions of customer behaviour. Another example is the management of an internet portal, which must be ready to handle possible Internet users` queries within a reasonable time, while having access to statistics describing Internet traffic.
Researchers are working on generalizing known results from approximation algorithms theory so that they can be used when part of the program input data is described only by the probability distribution.
"Some of the problems we are interested in have already been examined in probabilistic models, but with strong assumptions, for example concerning the independence of occurring events. We would like to get rid of such assumptions and develop a theory operating in the simplest possible model, on any probability distributions" - Włodarczyk explains.
In addition to building algorithms, scientists want to understand how the structure of the problem changes in the face of data uncertainty. They determine what properties the optimal solutions have. All this is expected to bring the theory of algorithms closer to practice.
PAP - Science in Poland, Karolina Duszczyk
kol/ ekr/ kap/
tr. RL
Przed dodaniem komentarza prosimy o zapoznanie z Regulaminem forum serwisu Nauka w Polsce.
