Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality.

Mohsen Bayati Devavrat Shah Mayank Sharma

Published in: IEEE Trans. Inf. Theory (2008)

Keyphrases

linear programming
max product
linear programming relaxation
belief propagation
linear program
sum product
np hard
convergence rate
message passing
feasible solution
maximum weight
graphical models
primal dual
loopy belief propagation
integer programming
column generation