FB6 Mathematik/Informatik/Physik

Institut für Informatik

Osnabrück University navigation and search

Main content

Top content

Theoretische Informatik

 Algorithm Engineering focuses on the gap between the purely theoretical analysis of algorithms and the practical run-time performance. Such gaps may arise, e.g., by hiding huge constants in the Big-O-notation; or by using the traditional von Neumann memory/machine model, even though current computers tend to have a deep memory hierarchy (caches, RAM, HDD) with different access speeds. Also, certain analyzed worst-case scenarios may be irrelevant for practical applications, and certain potentially beneficial input properties were not exploited.

Especially – and this is the main research focus of this group – when considering NP-hard optimization problems, it often turns out that by using suitable techniques, computing provable optimal solutions may not be as practically intractable as expected…