Fast b-matching via Sufficient Selection Belief Propagation
Bert Huang, Tony Jebara · 2011
This article describes scalability enhancements to a previously established belief propagation algorithm that solves bipartite maximum weight b-matching. The previous algorithm required O(|V | + |E|) space and O(|V ||E|) time,whereasweapplyimprovements to reduce the space to O(|V |) and the time to O(|V | 2.5)intheexpectedcase (though worst case time is still O(|V ||E|)). The space improvement is most significant in cases where edge weights are determined by a function of node descriptors, such as a distance or kernel function. In practice, we demonstrate maximum weight b-matchings to be solvable on graphs with hundreds of millions of edges in only a few hours of compute time on a modern personal computer without parallelization, whereas neither the memory nor the time requirement of previously known algorithms would have allowed graphs of this scale. 1