Abstract-Max-produkt "belief utbredning" (BP) är en iterativ, meddelande-passing algoritm för att hitta den maximala en posteriori (MAP) tilldelning av en diskret sannolikhetsfördelning som anges av en grafisk modell. Trots den spektakulära framgången för algoritmen inom många tillämpningsområden såsom iterativ avkodning och kombinatorisk optimering, som involverar grafer med många cykler, är teoretiska resultat om både korrekthet och konvergens av algoritmen kända i bara ett fåtal fall (se avsnitt I för referenser). I detta dokument kommer vi att bevisa riktigheten och konvergensen av max-produkt för att hitta maximal vikt matchning (MWM) i bipartit grafer. Även om den underliggande grafen av MWM problemet har många cykler, något överraskande visar vi att max-produkt algoritmen konvergerar till rätt MWM så länge MWM är unik. Vi tillhandahåller en gräns på antalet iterationer som krävs och visar att för en graf av storlek n, beräkningskostnaden för algoritmskalor som O (n 3 ), vilket är samma som beräkningskostnaden för de mest kända algoritmer för att hitta MWM. Vi ger också ett intressant samband mellan dynamiken i maxproduktalgoritmen och auktionsalgoritmen, som är en välkänd distribuerad algoritm för att lösa MWM-problemet. Index Terms-Auction algoritm, tro spridning (BP), distribuerad optimering, linjär programmering, Markov slumpmässiga fält, maximal vikt matchning (MWM), max-produkt algoritm, meddelande-passing algoritmer, min-sum algoritm.
Utmed dessa linjer under de senaste åren, meddelandepasserande algoritmer har använts för maximal vikt matchande problem i bipartit grafer REF.
Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science']}