Herzlich Willkommen!

Organtransplantationen, Schulplatzvergabe, Online-Dating, Auktionsmärkte: All diesen unterschiedlichen Bereichen ist gemein, dass Zuordnungen zwischen Akteuren getroffen werden müssen.

Wir haben uns ein Semester lang mit dem spannenden Feld der Matchingtheorie befasst und möchten dir dieses auf den folgenden Seiten ein wenig näher bringen. Unser Interesse gilt dabei besonders dem bipartiten Matching unter Präferenzen.

Viel Spaß beim Lesen wünscht das Studierenden-Projekt MatchUP der Arbeitsgruppe CSLog (Universität Bremen).

Grundlagen

Grundlagen Graphentheorie

Grundlegende Informationen zur Graphentheorie

Grundlagen Matchingtheorie

Was sind Matchings und welche Eigenschaften haben sie?

Arten von Matchings

Kardinalitätsmaximale Matchings

Finden kardinalitätsmaximaler Matchings mit dem Satz von Berge

Perfekte Matchings

Definition von perfekten Matchings und Übersicht einiger zentraler Sätze

Stabile Matchings

Stabile Matchings und blockierende Kanten

Gewichtsmaximale Matchings

Was sind gewichtsmaximale Matchings und wie können wie sie finden?

Netzwerke

Grundlagen

Was sind Netzwerke und welche Eigenschaften haben sie?

Maximale Flüsse

Wie können maximale Flüsse gefunden werden?

Minimale Schnitte

Was sind Schnitte und wieso sind sie interessant?

Matchings unter Präferenzen

Das School-Choice-Problem

Problembeschreibung, Notation, Eigenschaften von Algorithmen

Boston-Algorithmus

Einer der klassischen School-Choice-Algorithmen

Gale-Shapley-Algorithmus

Der Gale-Shapley-Algorithmus zum Finden von stabilen Matchings

Top-Trading-Cycle-Algorithmus

Ein Algorithmus für den Tauschhandel mit unteilbaren Gütern.

Fotoquellen:

Aerial View of City Under Cloudy Sky during Daytime Photo von Osman Rana, Unsplash, Unsplash Lizenz.
Red Apple Fruit on Four Pyle Books Photo von Element5 Digital, Unsplash, Unsplash Lizenz.
Grayscale Photography of Teacher Standing Near Chalkboard and Children Sitting on Chairs Photo von Austrian National Library, Unsplash, Unsplash Lizenz.
Yellow and Brown Leaves on White Ceramic Tiles Photo von Tolga Ulkan, Unsplash, Unsplash Lizenz.
Red Blocks on Brown Wooden Table Photo von Tierra Mallorca, Unsplash, Unsplash Lizenz.
Architectural Photography of Concrete Establishment von Miguel Sousa, Unsplash, Unsplash Lizenz.
Brown Wooden Ruler von Christian Kaindl, Unsplash, Unsplash Lizenz.
Two gold-colored rings on paper von Sandy Millar, Unsplash, Unsplash Lizenz.
italien-pisa-toskana-turm von jackmac34, Pixabay, Pixabay Lizenz.
Assorted-color yard threads von Omar Flores, Unsplash, Unsplash Lizenz.
River between brown rocky mountains during daytime von Logan Mayer, Unsplash, Unsplash Lizenz.
Person grinding pipe steel wool photography von Karan Bhatia, Unsplash, Unsplash Lizenz.
Two gray dumbbells von Cyril Saulnier, Unsplash, Unsplash Lizenz.