Modern computer systems enable expanding application areas in many respects:
- Parallel computer networks make dealing with extremely complex algorithmic problems possible.
- The Internet realizes global exchange of information and could potentially be used as one giant parallel computing device.
- Wireless connected systems allow flexible communication between mobile stations.
- Hardware support for graphic applications enables real-time navigation in complex virtual scenes.
A special challenge is posed by computing systems consisting of heterogeneous components (e.g. differently powerful processors, storage devices or communication capabilities) with structural changes over time. Our research focuses on the algorithmic challenges imposed by the realization and efficient usage of such heterogeneous, dynamic systems.
Parallel Computing: Peer-to-Peer Based Web Computing
Computer networks can potentially supply nearly unlimited parallel computing power. However, the efficient use of these networks is an extremely complex problem. Meanwhile, our PUB-library is used by an international community of developers. Our Web computing library PUBWCL now goes one step further and uses the Internet as a parallel computer. Some of the main challenges are the peer-to-peer based construction and the necessary dynamic load balancing strategies.
Computer Graphics: Real-Time Navigation in Giant Scenes
In order to be able to navigate in a virtual three dimensional space and to give a realistic optical impression of the changing scene, enormous demands are imposed on the underlying data structures that handle the scene and facilitate the rendering of the individual pictures. Currently we focus on the development of methods for choosing the most efficient applicable rendering method during runtime, dependent on the position and viewing direction. First we work on methods that decide whether it is worthwhile to use culling methods. Moreover, we are exploring the capabilities of our algorithms in applications from Business Computing, in cooperation with partners from the Heinz Nixdorf Institute.
Local Strategies in Dynamic Networks: The New Challenge
Dynamic networks, i.e., networks whose nodes change their (geometric, geographic) position over time, play a major role in many areas: They can, e.g., be used as data structures for moving objects in Computer Graphics, as models for wireless mobile communication networks or as mobility patterns for robotic explorations. We investigate the exploration of an unknown terrain by a large group of robots as an example application scenario. Again, the task to design local strategies that yield globally good behavior is a major challenge.
Algorithmic Game Theory and Pricing
Algorithmic pricing encompasses a wide range of combinatorial optimization problems with applications in the computation of revenue maximizing pricing schemes based on data about the preferences of potential customers, as well as the design of incentive compatible auction mechanisms for strategic settings - one of the fundamental problems of algorithmic game theory. We consider algorithmic aspects of these problems with a focus on approximation and randomization techniques - two central paradigms in the design and analysis of algorithms.
Randomization: A Basic Algorithmic Technique
The algorithmic work described above has shown us that using randomized procedures can produce amazing gain in efficiency. Therefore we systematically study the potential of randomized algorithms and develop or apply methods of probability theory for analyzing them.
Our Teaching: Closely Linked to Research
Our courses cover methods and concepts of the development and analysis of efficient algorithms. We also run project groups and support diploma theses that extend and apply our theoretical insights in order to design efficient algorithms and libraries.
