Combinatorial Geometry

Matroids

Matroids form a combinatorial model for linear independence. Given a finite set E and a subset of its d-element subsets, these form the bases of a matroid if and only if they satisfy the Steinitz exchange axiom of linear algebra

If B1, B2 are bases and e is an element in B1\B2, then there exists an element f in B2\B1 such that B1 - e + f is a basis again.

Matroids arise not only from points in vector spaces but also from graphs, transversal systems, matchable sets and many others.

Among others we examined the structure of the set of circuits in binary matroids (with Jackson B: Large Circuits in Binary Matroids of Large Cogirth: I. andII.), (with Nešetřil J: A Note on MaxFlow-MinCut and Homomorphic Equivalence in Matroids). Also we discovered them in a problem motivated by a real world application (with Epping T, Lübecke M E: Max-Flow Min-Cut Duality for a Paint Shop Problem).

Oriented Matroids

While matroids have the flavour of set systems, oriented matroids always model a geometric situation. Oriented matroids model e.g. convexity or digraphs.

Recently we considered generalizations of flows in digraphs to oriented matroids (with Goddyn L, Hlineny P: Balanced Signings of Oriented Matroids and Chromatic Number), (with Nickel R: The Flow Lattice of Oriented Matroids).

Game Theory

Cooperative Game Theory

In cooperative game theory we have a set of players S that can form coalitions K. Such a coalition receives a payment v(K). One of the main issues of cooperative game theory is to determine solution concepts, i.e. how to allocate the money to the players in the coalition. Of particular interest are allocations of v(S), the value of the grand coalition of all players, with the property that no coalition has an incentive to split from the grand coalition. We call such a solution stable.

Our main focus is the computational complexity of solution concepts of games where the payoff of a coalition is defined by some problem from combinatorial optimization, such as matching or travelling salesman (with Faigle U, Fekete S, Kern W: On the Complexity of Testing Membership in the Core of Min-cost Spanning Tree Games), (with Faigle U, Kern W, Fekete S: The Nukleon of Cooperative Games and an Algorithm for Matching Games), (with Jin H, Nickel R: The Hungarian Method for a Mixed Matching Market).

Graph Coloring Games

In coloring games two players, the maker and the breaker, alternatingly color vertices or edges of a graph with a given set of k colors feasibly. If in the end the graph is completely colored the maker wins. The breaker aims at enforcing a blocking situation where there are uncolored elements that cannot be feasibly colored without introducing an extra color.

We examine how many colors are necessary in certain graph classes such that the maker always has a winning strategy (with Erdös P, Faigle U, Kern W: Note on the Game Chromatic Index of Trees).
Learn more about coloring games at our homepage of Graph Coloring Games.

Algorithmic Graph Theory

Graphs with few P4

Graphs without induced path on four vertices, so called cographs, can be encoded in a labeled tree. Using this data structure several optimization problems that are NP-complete in general can be solved efficiently or even in linear time. This property is invariant if only few P4 are present (with Tinhofer G: Hamiltonicity in Graphs with few P4s). Also matrix partition problems can be efficiently solved on cographs (with Feder T, Hell P: Generalized Colorings (Matrix Partitions) of Cographs).

This is the first non-trivial class of graphs where these general coloring problems are easy.

Sequencing in Logistics

Scheduling of production lines in car manufacturing

In Europe cars are individually manufactured by order. This way the lots vary substantially and the order in which the cars are built has a huge impact on cost and quality.

Starting from the problem to reduce the number of color changes in the paint shop (with Epping T, Oertel P: Complexity Results on a Paint Shop Problem), we developed a new algorithm to do the full sequencing. An implementation of our method is used in plants all over Europe (with Epping T, Nickel R, Oertel P: Order Sequencing in the Automobile Industry).

Vehicle Routing with realistic side constraints

The task to route a fleet of vehicles with capacity constraints at minimmal cost is computationally hard already for small to medium sized problems (with Blasum U: Application of Branch and Cut to the Capacitated Vehicle Routing Problem). In real world problems additionally several side constraints like time windows have to be considered.

We developed several heuristics for that purpose (with Bachem A, Malich M: The Simulated Trading Heuristic for Solving Vehicle Routing Problems), (with Hamacher A, Moll C: Tree Partitioning under Constraints – Clustering for Vehicle Routing Problems). One of our methods is used for the strategic planning of the distribution of newspapers.