Gewichtetes Bipartites Matching

Das gewichtete bipartite Matching (Weighted Bipartite Matching) ist das Problem der Operations Research, in einem bipartiten Graphen mit zwei disjunkten Knotenmengen U und V, bei dem jede mögliche Kante (u,v) ein Gewicht trägt, die Kantenmenge mit maximalem (oder minimalem) Gesamtgewicht zu finden, sodass kein Knoten mehr als eine Kante berührt. Es ist der allgemeinste Matching-Rahmen in der kombinatorischen Optimierung; Spezialfälle: der quadratische, ausgeglichene Fall (|U| = |V|) ist das **Zuordnungsproblem**, gelöst durch die Ungarische Methode (Kuhn 1955; Munkres 1957) in polynomieller Zeit O(n³); der rechteckige Fall (|U| ≠ |V|) wird durch Dummy-Knotenerweiterung behandelt; das allgemeinere Maximum-Gewicht-Matching, in dem auf jeder Seite Knoten ungematcht bleiben dürfen, hat eine eigene Algorithmenfamilie. Algorithmen: gewichtetes Maximum-Matching ist polynomiell (Edmonds 1965 und später); der klassische Zuordnungsfall wird mit der Ungarischen Methode O(n³) gelöst, und LAP (Jonker-Volgenant 1987) ist in der Praxis schneller. Feldanwendungen: Mitarbeiter-Aufgaben-Zuordnung, Kunden-Techniker-Matching, Anzeigenplatzierung, Online-Bipartite-Matching (#034), Gebot-Paket-Matching. Burkard, Dell'Amico und Martello (2009) ist die kanonische Referenz.