DFG Research Group
Flexible Online Algorithms
Address
- RWTH Aachen
Lehrstuhl für Informatik 1
D-52056 Aachen - Phone: +49 241 80 21101
- Fax: +49 241 80 22216
Group Members
- Faculty
- Research Assistants
- Secretary
- Former Members
Project
Online algorithms studied in theory are characterized by the fact that they do not have knowledge about the whole input sequence of jobs in advance. Instead, the input sequence is generated job by job, and a new job is not issued until the previous one is handled by the online algorithm. In real applications, jobs can usually be delayed for a short amount of time, and hence the input sequence of jobs can be rearranged in a limited fashion to optimize the performance. This flexible online scenario occurs in many applications in computer science and economics, e.g., in computer graphics: A rendering system displays a sequence of primitives. The number of state changes of such a system are a significant factor for the performance. State changes occur when two consecutively rendered primitives differ in their attribute values, e.g., in their texture or shader program. With the help of a reordering buffer in which primitives can be buffered the sequence of primitives can be reordered online in such a way that the number of the state changes is reduced.