Browse Theses

In dieser Arbeit fokussieren wir uns auf Matching- und Flussprobleme auf Instanzen mit Präferenzen. Es werden Märkte mit Hilfe von kombinatorischer Optimierung durch Graphen modelliert. Während Hersteller, Händler und Verbraucher durch Knoten repräsentiert werden, sind die möglichen Geschäfte zwischen ihnen als Kanten veranschaulicht. Abhängig von der Struktur des Marktes wird einen Warenfluss oder eine Händlerpaarung gesucht. Das grundlegende Prinzip ist immer das gleiche: Stabilität. Eine Marktsituation ist stabil, wenn kein Paar von Händlern existiert, die die Situation bei gegenseitiger Zustimmung ändern möchten. Abhängig von der Komplexität des Problems unterscheiden wir drei Instanzen: Matching-, Allokations- und Flussinstanz. Die Spätere kann immer als Verallgemeinerung der Frühere betrachtet werden. Eine stabile Lösung zu finden ist in allen drei Problemen bewältigbar. Kapitel 1: Grundlagen in stabilen Matchings. Das Konzept Stabilität wird eingeführt und die wichtigsten Resultate aus der Literatur werden erwähnt. Wir geben Beispiele für Anwendungen. Kapitel 2: Stabile Matchings mit beschränkten Kanten. In diesem Kapitel analysieren wir Matchingsprobleme auf bipartiten und nichtbipartiten Graphen, die beschränkte Kanten enthalten. Eine beschränkte Kante ist entweder erzwungen oder verboten. Wir betrachten zwei Approximationskonzepte und bieten eine komplette Analyse aller möglichen Fällen an. Kapitel 3: Weitere Komplexitätsresultate für stabilen Matchings. Hier werden zwei weitere Probleme auf Matchingsinstanzen diskutiert. In dem ersten suchen wir ein Matching mit freien Kanten, das maximale Kardinalität hat. In der zweiten Hälfte des Kapitels wird ein stabiles Matching in nichtbipartiten Graphen mit Gleichstand in Präferenzlisten gesucht und NP-Härte gezeigt. Kapitel 4: Pfade zur stabilen Allokationen. Das stabile Allokationsproblem ist eine kapazitierte Variante des stabilen Matchingsproblems. In diesem Kapitel stellen wir die Frage, ob random und deterministische Prozesse auf unkontrollierten Märkten terminieren. Laufzeiten der besser und best response Strategien sind analysiert. Kapitel 5: Nicht teilbare stabile Allokationen. Eine natürliche Erweiterung des stabilen Allokationsproblems ist die ganzzahlige Variante: Hier sucht man Allokationen, in den Elemente nicht geteilt werden. Wir zeigen dass das Problem in Polynomialzeit bewältigbar ist und präsentieren einen Rundungsalgorithmus. Kapitel 6: Stabile Flüsse. Wie Matchingsprobleme in allgemeinen, stabile Matchings können auch auf Flussinstanzen verallgemeinert werden. Wir präsentieren einen polynomialen Algorithmus, eine Methode für stabile Flüsse mit beschränkten Kanten und einen Beweis für die Härte integraler multicommodity Flüssen. Kapitel 7: Populäre Matchings. In dem letzten Kapitel wird eine Alternative zur stabilen Matchings diskutiert. Die Komplexität von zwei Problemen in dem Thema wird betrachtet.