Algorithmes rapides pour trouver des appariements optimaux sur les graphes bipartis pondérés

Question

Je dois résoudre le problème d'affectation (compte tenu d'un graphe bipartite complet pondéré, choisir un appariement parfait avec le poids total maximum) et j'utilise le O (n^3) version d'ici http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm. Cependant, un article que j'ai lu a mentionné une «méthode plus efficace» dans «Un algorithme de chemin d'augmentation le plus court pour les problèmes d'affectation linéaire dense et clairsemée», qui est malheureusement derrière un paywall. Y a-t-il des algorithmes plus rapides dont je devrais être au courant (soit asymptotiquement, soit juste avec des constantes plus petites/accès à la mémoire plus uniforme ou quoi que ce soit d'autre)? Je travaille avec des poids à virgule flottante plutôt qu'avec des poids entiers, ce qui pour la méthode hongroise ne semble pas avoir d'importance, mais pourrait être un problème pour des implémentations d'entiers plus rapides. Tous les liens pertinents seraient très appréciés.

Answer 1

il peut être également converti en problème de débit max min débit, vous pouvez vérifier cela.

AFAIK, hongrois est le plus rapide.

Answer 2

Il existe quelques papiers qui ont des algorithmes rapides pour les graphiques bipartites pondérés. Un article récent Ramshaw et Tarjan, 2012 "sur les affectations de coûts minimums dans les graphiques bipartites déséquilibrés" présente un algorithme appelé FlowAssign et Refine qui résout le problème d'allocation de coût min, déséquilibré, bipartite et utilise l'échelle de poids pour résoudre le problème. problèmes d'affectation parfaits et imparfaits, mais pas incrémentaux avec une complexité d'exécution de O (m * sqrt (n) * log (n * C)) où m est le nombre de bords (aka arcs) dans le graphique, n est le nombre maximal de nœuds dans les deux graphiques à apparier, C est une constante supérieure ou égale au maximum poids de bord et est supérieure ou égale à 1.

La mise à l'échelle du poids est ce qui permet à l'algorithme d'atteindre de bien meilleures performances en ce qui concerne s où s est le nombre de nœuds appariés.

D'autres solutions rapides peuvent être trouvées au début des années 1990. Un document de 1993 intitulé « QuickMatch: un algorithme très rapide pour le problème d'affectation » par Lee et Orlin propose un algorithme dont l'exécution, ils estiment aussi efficacement linéaire sur la taille du graphique en termes d'arcs. http://jorlin.scripts.mit.edu/docs/publications/WP4-quickmatch.pdf

L'algorithme QuickMatch résout le problème d'affectation comme une séquence de n problèmes les plus courts de chemin. Ils utilisent alternativement chemins les plus courts entre les nœuds d'origine et les nœuds de destination ainsi que des heuristiques pour diminuer le nombre de calculs. Les auteurs estiment la complexité d'exécution moyenne par des résultats empiriques et des comparaisons avec des algorithmes théoriquement limités . Ils trouvent que leur algorithme est linéaire w/le nombre des bords de graphique (a.k.a. arcs), mais l'algorithme est pas aussi performant que l'algorithme "forward-reverse auction" de Bertsekas qui utilise également alternant les chemins les plus courts.La référence au plus tard n'a pas été imprimé dans le journal, mais peut-être dans « algorithmes d'enchères inversées pour des problèmes d'affectation », Castañón, 1992, MACS Seris en mathématiques discrètes et informatique

Il y a aussi l'algorithme que le code de référence de segmentation de Berkeley utilise pour l'appariement bipartite pendant l'évaluation des résultats de la segmentation par rapport aux limites tracées par l'homme. http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ Ils utilisent le paquet CSA Goldberg http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/code/CSA++/ qui aurait l'exécution qui est linéaire avec la taille du graphe et résout pour l'attribution clairsemés coût minimum. Les références sont "Un algorithme efficace de mise à l'échelle des coûts pour le problème d'attribution", 1993 par Goldberg et Kennedy et Cherkassky et Goldberg, "Sur la mise en œuvre de PushRelabel Procédé pour le problème d'écoulement maximal," Proc. Quatrième Programmation entière et optimisation combinatoire Conf, pp 157- 171, mai 1995.