# Main content

## Top content

#### Contact Details

Universität Osnabrück

Institut für Mathematik

Institut für Informatik

D-49069 Osnabrück

gkgn@uni-osnabrueck.de

#### Spokesman

Prof. Dr. Markus Chimani

Tel.: +49 541 969 2478

Fax: +49 541 969 2799

markus.chimani@uni-osnabrueck.de

## Research Projects

**Cut-Polytopes and Colorings**: Chimani, Juhnke-Kubitzke, Reitzner, Römer

**Optimization Problems on Graphs with Special Structures**: Chimani, Juhnke-Kubitzke, Knust

Many graph optimization problems like the TSP or graph coloring problems are in general NP-hard. However, in practical applications the graphs often have special structures (e.g., they may be bipartite, planar, trees, comparability graphs, etc. or the underlying cost matrices satisfy special properties) which allow the development of more efficient algorithms. The objective of this project is to study graph optimization problems with special structures, derive new complexity results and develop efficient solution algorithms. One specific subproject in this context are approximation algorithms for special graph partitioning problems.

**Mobility Modeling**: Aschenbruck, Döring

Modeling of human mobility is a relevant topic in several scientific areas. In computer science, it is of high interest, e.g., due to its significant impact on performance evaluation in wireless communication networks. Several models have been proposed and validated by traces. The more complex a model the less scalable the simulative performance evaluations are. Thus, analytical performance assessment is of interest. Analyzing mathematical properties of more complex models (e.g., graph-based models) is an open challenge.

**Optimization under Uncertainties**: Döring, Knust, Reitzner

In practice, data is often not known exactly and can only be estimated (e.g., by distribution functions or intervals for certain parameters). Then, the goal of optimization is to use this information such that better solutions are obtained than when uncertainties are ignored. The objective of this project is to develop the theoretical background and solution methods integrating data uncertainties in an appropriate way (stochastic optimization, different robustness concepts). The concepts are to be evaluated in connection with applications in practice.