Approximation and On-line Algorithms
Associated Researchers: Dr. T. Erlebach
Many fundamental optimisation problems that are encountered in applications have been proved to be NP-hard. Examples are the travelling salesperson problem (TSP), the knapsack problem, or the bin-packing problem. NP-hardness implies that it is extremely unlikely that we can find algorithms that solve these problems optimally in polynomial time. Therefore, we are interested in designing algorithms that run efficiently and always produce solutions that need not necessarily be optimal, but that must be provably close to the optimum. Such algorithms are called approximation algorithms, and the worst-case bound on the deviation from the optimum is called the approximation ratio. The goal of this research is to design and analyse approximation algorithms achieving approximation ratios that are as small as possible. In particular, we are investigating approximation algorithms for problems from areas such as scheduling, routing, resource allocation, network optimisation, and computational biology.
A different situation where it is infeasible to compute optimal solutions arises if full knowledge about the problem instance is not available to the algorithm. This is called an on-line scenario. For example, consider a web cache that stores a set of web pages. When a user requests a page that is currently in the cache, the page can be served directly from the cache. Otherwise, the page must be obtained from the originating web server before it can be served to the user, and this takes a much longer time and creates much more traffic in the Internet. The cache can store this new page, but may have to evict another stored page to make space for it. The difficulty lies in deciding which page to evict. It would be ideal to keep those pages in the cache that will be accessed frequently in the future, but the requests made by users in the future are unknown to the caching algorithm. Thus, the algorithm has to deal with an on-line problem. Using competitive analysis, the solution produced by an on-line algorithm is compared to the optimal off-line solution. The worst-case deviation from the optimum is called the competitive ratio. Again, the research goal is to design algorithms that have the smallest possible competitive ratio. Here, our current interests are in on-line problems arising in communication networks.
Approximation and on-line algorithms have been a flourishing research area in the last 10-15 years, and substantial insights have been gained. Nevertheless, there are several significant and fundamental open problems that need to be addressed. Besides, as the application areas are continuously evolving, new optimisation problems are encountered that often require the development of new techniques for designing approximation or on-line algorithms.