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

Finding maximal cuts in a (weighted) graph is a classical problem in combinatorial optimization with applications in many fields including algebraic statistics, statistical physics, chip design, and network flows. Although this problem is NP-hard in general, for special classes of graphs (e.g., planar graphs) polynomial time algorithms exist and facet descriptions of the underlying cut polytope are known. The objective of this project is to study the max-cut problem for graphs that have a small, i.e., fixed, chromatic number. This includes deriving combinatorial properties of the cut polytope as well as complexity results and developing (approximation) algorithms.

Optimization Problems on Graphs with Special Structures: Chimani, Juhnke, 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. Specific subprojects in this context are approximation algorithms for special graph partitioning problems and storage loading problems with stacking constraints and/or stochastic uncertainties.

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.