Gewichtetes Matching: Optimale Paare mit Kantengewichten

Beim gewichteten Matching (auch optimales Matching) tragen die Kanten eines Graphen Zahlenwerte — etwa Kosten, Zeit oder Ähnlichkeiten. Gesucht ist dann nicht mehr irgendein Matching, sondern eines mit maximalem Gesamtgewicht. Es ist damit das Optimierungs-Pendant zum reinen Existenzproblem des Matchings.

Abgrenzung: maximal, maximum und gewichtet

Maximales Matching: Eine Kante kann nicht mehr hinzugefügt werden, ohne die Matching-Eigenschaft zu verletzen — aber die Kantenanzahl ist nicht unbedingt am größten.
Maximum-Matching: Die Anzahl der Kanten ist maximal, ungeachtet der Gewichte.
Gewichtetes Matching: Das Gesamtgewicht der gewählten Kanten ist maximal — je nach Gewichtung können dabei auch weniger Kanten als im Maximum-Matching gewählt werden.

Das Zuordnungsproblem und die Ungarische Methode

Der wichtigste Spezialfall ist das Zuordnungsproblem (Assignment Problem): n Aufgaben sollen so an n Bearbeiter verteilt werden, dass jeder genau eine Aufgabe bekommt und die Gesamtkosten minimal sind. Modelliert wird das als perfektes, gewichtetes Matching in einem bipartiten Graphen mit n+n Knoten und einer Kostenmatrix. Die Standardlösung ist die Ungarische Methode (Kuhn 1955, Verbesserung durch Munkres), die das Problem in O(n³) löst.

Komplexität

Auch für allgemeine (nicht bipartite) Graphen ist das gewichtete Matching polynomial lösbar: Der gewichtete Blossom-Algorithmus von Edmonds findet ein Matching maximalen Gewichts in O(V³). Damit gehört die gewichtete Paarung zu den wenigen Optimierungsproblemen auf Graphen, die trotz ihrer Komplexität effizient berechenbar sind.

Anwendungen

Personal- und Ressourcenplanung: Mitarbeiter mit Qualifikationen und Kosten optimal auf Aufgaben verteilen.
Transport- und Logistikoptimierung: Standorte und Lieferziele so paaren, dass die Gesamtstrecken minimal werden.
Datenassoziation in der Bildverarbeitung: Gemessene Punkte mit erwarteten Objekten anhand von Ähnlichkeitsgewichten abgleichen.