Sei G = (V,E) ungerichtet, bipartit, gewichtet mit c : E .
(z.B. c(i,j) = Glücksgefühl bei Paarung Mann i / Frau j )
Gesucht: Maximum cost matching z.B.:
Idee: Suche alternierende Wege, die die Gesamtkosten erhöhen.
Variante: Suche perfektes Matching mit minimum cost.
Problem: Zuordnungsgewicht zwischen i und j wird von i und j unterschiedlich gesehen.
Antwort: Ranking (d.h. statt absoluter Werte eine Reihenfolge 1,2,... festlegen, also eine Beliebtheitsskala bzw. Präferenzliste erstellen)