Populäre Matchings und stabile Paarungen
von Felix Neumann.
Literaturarbeit zu einer Veröffentlichung von Huang und Kavitha in 2011. Entstanden im Rahmen des Hauptseminars im Wintersemester 2011⁄12 am FG Komplexitätstheorie und Effiziente Algorithmen der Technischen Universität Ilmenau.
Zusammenfassung
Ein in der Informatik häufig anzutreffendes Problem ist die Paarung von Objekten, bekannt als Matching- oder Hochzeitsproblem. Reale Anwendungsfälle sind etwa die Zuordnung von Konsumenten auf Produzenten, von Bewerben auf verfügbare Stellen oder die Zuordnung im Rahmen einer Partnervermittlung. Dabei kann es vorkommen, dass die Objekte bestimmte Paarungen bevorzugen. Als populär bezeichnet man die Lösung eines Matchingproblems dann, wenn keine andere Lösung existiert, welche eine Mehrheit der Objekte der populären Lösung vorziehen würden. Zu einem Matchingproblem können möglicherweise populäre Lösungen verschiedener Kardinalität existieren, d.h. es wurden eine unterschiedliche Anzahl an Objekten gepaart. Bisher waren dabei vorallem populäre Matchings minimaler Kardinalität (stabile Matchings) bekannt, bei welchen keine zwei Objekte existieren, die nicht miteinander gepaart sind, sich aber gegenseitig ihrer tatsächlichen Paarung bevorzugen würden. Daneben existieren jedoch auch populäre Matchings höherer Kardinalität, bei welchen derartige „instabile“ Paarungen zugunsten der Popularität der gesamten Lösung in bestimmtem Maße akzeptiert werden.
Die hier nachvollzogene Arbeit Huang, Kavitha 2011: Popular Matchings in the Stable Marriage Problem beschäftigt sich mit der Frage, wie solche populäre Lösungen maximaler Kardinalität berechnet werden können und stellt hierzu einen effizienten Algorithmus vor. Zudem zeigen die Autoren des Papers eine Methode auf, um eine gegebene Lösung eines Matchingproblems in Linearzeit auf ihre Popularität hin zu testen.