Kombinatorische Geometrie

Matroide

Matroide bilden ein kombinatorisches Modell für lineare Unabhängigkeit. Hat man eine endliche Menge E und eine Teilmenge der d-elementigen Teilmengen, so bilden diese das System der Basen eines Matroids, wenn sie das Steinitzsche Basisaustauschaxiom der linearen Algebra erfüllen

Sind B1, B2 Basen und ist e ein Element aus B1\B2, so gibt es ein Element f aus B2\B1 so dass B1 - e + f wieder eine Basis ist.

Man unterscheidet verschiedene Matroidklassen, je nachdem, ob sie etwa durch Graphen oder Punktmengen definiert sind.

Wir haben unter anderem die Struktur von Kreisen in binären Matroiden untersucht (mit Jackson B: Large Circuits in Binary Matroids of Large Cogirth: I. and II.), (mit Nešetřil J: A Note on MaxFlow-MinCut and Homomorphic Equivalence in Matroids). Diese tauchen aber auch in Problemen aus Anwendungen auf (mit Epping T, Lübecke M E: Max-Flow Min-Cut Duality for a Paint Shop Problem).

Orientierte Matroide

Während Matroide oft nur als Mengensysteme analysiert werden, modellieren orientierte Matroide stets eine geometrische Situation. Man kann sie als Hyperebenenarrangements auffassen, bei denen in den Hyperebenen leichte Deformationen erlaubt sind. Orientierte Matroide modellieren Konvexität oder auch Digraphen.

In letzter Zeit haben wir vor allem Verallgemeinerungen von Flüssen in Digraphen auf orientierte Matroide untersucht (mit Goddyn L, Hlineny P: Balanced Signings of Oriented Matroids and Chromatic Number), (mit Nickel R: The Flow Lattice of Oriented Matroids).

Spieltheorie

Kooperative Spieltheorie

In der kooperativen Spieltheorie hat man eine Menge von Spielern S, die Koalitionen K bilden können. Eine solche Koalition erhält dann eine Auszahlung v(K). Eine zentrale Fragestellung der kooperativen Spieltheorie ist es dann, diese Auszahlung in der Koalition zu verteilen. Insbesondere ist man an Verteilungen der Auszahlung v(S) der großen Koalition aller Spieler interessiert, die niemandem einen Anlass bietet, die Koalition zu verlassen, da zum Beispiel Teilkoalitionen eine höhere Auszahlung erhalten würden, als sie bei der Verteilung bekommen. Eine solche Verteilung nennt man stabil.

Wir untersuchen vor allem Spiele, bei denen die Auszahlungsfunktion durch ein kombinatorisches Optimierungsproblem definiert ist. Dabei interessieren wir uns für effiziente Algorithmen, mit denen man eine solche Auszahlung berechnet (mit Faigle U, Fekete S, Kern W: On the Complexity of Testing Membership in the Core of Min-cost Spanning Tree Games), (mit Faigle U, Kern W, Fekete S: The Nukleon of Cooperative Games and an Algorithm for Matching Games), (mit Jin H, Nickel R: The Hungarian Method for a Mixed Matching Market).

Graphenfärbungsspiele

Bei einem Färbungsspiel hat man einen Graphen gegeben, eine endliche Menge Farben und zwei Spieler, den Maker und den Breaker. Abwechselnd färben die Spieler Elemente des Graphen (Knoten oder Kanten), wobei übliche Zulässigkeitsbedingungen zu berücksichtigen sind. Ist am Ende des Spiels der Graph gefärbt, so hat der Maker gewonnen. Der Breaker hingegen ist bestrebt, eine Blockadesituation herzustellen, in der kein weiteres ungefärbtes Element zulässig gefärbt werden kann.

Wir untersuchen, wie viele Farben in gewissen Graphenklassen notwendig sind, damit der Maker eine Strategie hat, bei der er stets gewinnt (mit Erdös P, Faigle U, Kern W: Note on the Game Chromatic Index of Trees).
Mehr über Färbungsspiele finden Sie auf unserer Homepage der Graphenfärbungsspiele.

Algorithmische Graphentheorie

Graphen mit wenigen P4

Graphen ohne induzierten Weg mit vier Knoten, so genannte Cographen, lassen sich als gelabelter Baum kodieren. Mit dieser Datenstruktur lassen sich viele Optimierungsprobleme, die ansonsten NP-vollständig sind, effizient, meist sogar in Linearzeit lösen. Dies ändert sich nicht, wenn man wenige P4 zulässt (mit Tinhofer G: Hamiltonicity in Graphs with few P4s). Auch Matrixpartitionierungs-Probleme lassen sich auf Cographen effizient lösen (mit Feder T, Hell P: Generalized Colorings (Matrix Partitions) of Cographs).

Dies ist die erste nicht-triviale Graphenklasse, von der gezeigt werden konnte, dass solche verallgemeinerten Färbungsprobleme effizient lösbar sind.

Sequenzierungsprobleme in der Logistik

Reihenfolgeplanung im Automobilbau

In Europa werden Automobile nach Bestellung durch den Kunden individuell gefertigt. Da so die Anforderungen in der Produktion an die einzelnen herzustellenden Autos stark schwanken, hat die Reihenfolge der Herstellung einen großen Einfluss auf die Qualität und die Kosten.

Ausgehend von der Fragestellung, wie man unter weitestgehend vorgegebenen Reihenfolgen der Autotypen die Anzahl der Farbwechsel in der Lackiererei minimieren kann (mit Epping T, Oertel P: Complexity Results on a Paint Shop Problem), haben wir schließlich ein Verfahren entwickelt, das die volle Reihenfolgeplanung (Kiosk-Präsentation zum 30jährigen Jubiläum der FU Hagen) durchführt und in ganz Europa von einem großen Hersteller eingesetzt wird (mit Epping T, Nickel R, Oertel P: Order Sequencing in the Automobile Industry).

Vehicle Routing unter realistischen Nebenbedingungen

Das Problem, mit einer Flotte von Fahrzeugen mit Kapazitätsbeschränkungen eine vorgegebene Distribution aus einem Depot kostenminimal abzuwickeln, ist auch für relativ kleine Probleme noch nicht exakt lösbar (mit Blasum U: Application of Branch and Cut to the Capacitated Vehicle Routing Problem). In der Praxis ist man deshalb, insbesondere da auch zahlreiche Nebenbedingungen – wie etwa Zeitfenster – zu berücksichtigen sind, auf Heuristiken angewiesen (mit Bachem A, Malich M: The Simulated Trading Heuristic for Solving Vehicle Routing Problems), (mit Hamacher A, Moll C: Tree Partitioning under Constraints – Clustering for Vehicle Routing Problems). Ein mit uns entwickeltes Verfahren wird erfolgreich bei der strategischen Planung der Zeitungsdistribution (Kiosk-Präsentation zum 30jährigen Jubiläum der FU Hagen) eingesetzt.