PAAL · Practical Approximation Algorithms

The goal of this proposal is the development and study of practical approximation algorithms. We will base our study ontheoretical models that can describe requirements for algorithms that make them practically efficient. We plan to develop anefficient and useful programming library of approximation algorithms.Our research on approximation algorithms will be concentrated on two main topics:- multi-problem optimization, when the solution has to be composed out of different problems that need to interact,- interplay between regular and random structure of network that could allow construction of good approximation algorithms.The above concepts try to capture the notion of effective algorithms. It has to be underlined that they were not studied before.The practical importance of these problems will be verified by the accompanying work on generic programming conceptsfor approximation algorithms. These concepts will form the basis of universal library that will include Web algorithms andalgorithms for physical applications.