Schnellere maximale Gewicht-Matching-Algorithmus in bipartite Grafik

Question

Ich muss eine maximale Gewicht übereinstimmen in bipartite Graphen. Die Knoten jeder Seite sind beide auf der Ebene von 10^3. Das Diagramm ist global dünn und lokal dicht. (Ich weiß nicht, ob dies irgendeinen Einblick geben wird. Sie können dies ignorieren und das Problem als eine maximale Gewichtsanpassung in einem vollständigen Graphen sehen.)

Ich weiß, dass KM (Kuhn-Munkres-Algorithmus) O (n^3) und jetzt wird es benutzt. Das Problem ist, dass ich diese Aufgabe schneller machen will und kontrollierbare Verluste von weniger als 5% toleriere.

Ich habe einen linearen Approximationsalgorithmus aus "Linear-Zeit-Approximation für maximale Gewichtsanpassung" (2014) versucht, der 1-Epsilon in O (m/epsilon * log (1/Epsilon)) erreicht. Es scheint gut, aber ich implementiere es und finde es schlechter als KM in der Zeit und manchmal sind seine Ergebnisse schlechter als die Ergebnisse des Greedy-Algorithmus. :( (edit: das Papier ist für die allgemeine grafische Darstellung, aber ich vereinfache es das zweiteilige Graphen, so dass der betreffende Teil Blüte irrelevant jetzt ist)

weiß jemand von euch So haben manche Algorithmen können praktisch die KM outperform Algorithmus? Oder irgendwelche Papiere sind vielversprechend. Vorschläge sind willkommen!

vielen Dank!

Answer 1

die Frage teilweise beantworten zu können, die Veröffentlichung Approximating Maximum Weight Matching in Near-linear Time von Duan & Pettie stellt einen Approximationsalgorithmus für das maximale Gewicht im allgemeinen passend Graphen

Darüber hinaus verweist der Artikel auf die Veröffentlichung "An n^{5/2} Algorithmus für maximale Matchings in bipartite Graphen" von Hopcroft & Karp von 1973 (Referenz [25]), die eine Laufzeitkomplexität besser als n^3 ergeben würde. Aus dem Titel allein ist jedoch nicht ersichtlich, ob sich dies auf den gewichteten oder den ungewichteten Fall bezieht.