|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Belief propagation : an asymptotically optimal algorithm for the random assignment problem | | Justin Salez
; Devavrat Shah
; | | Date: |
3 Feb 2009 | | Abstract: | The random assignment problem asks for the minimum-cost perfect matching in
the complete $n imes n$ bipartite graph $Knn$ with i.i.d. edge weights, say
uniform on $[0,1]$. In a remarkable work by Aldous (2001), the optimal cost was
shown to converge to $zeta(2)$ as $n oinfty$, as conjectured by M’ezard and
Parisi (1987) through the so-called cavity method. The latter also suggested a
non-rigorous decentralized strategy for finding the optimum, which turned out
to be an instance of the Belief Propagation (BP) heuristic discussed by Pearl
(1987). In this paper we use the objective method to analyze the performance of
BP as the size of the underlying graph becomes large. Specifically, we
establish that the dynamic of BP on $Knn$ converges in distribution as
$n oinfty$ to an appropriately defined dynamic on the Poisson Weighted
Infinite Tree, and we then prove correlation decay for this limiting dynamic.
As a consequence, we obtain that BP finds an asymptotically correct assignment
in $O(n^2)$ time only. This contrasts with both the worst-case upper bound for
convergence of BP derived by Bayati, Shah and Sharma (2005) and the best-known
computational cost of $Theta(n^3)$ achieved by Edmonds and Karp’s algorithm
(1972). | | Source: | arXiv, 0902.0585 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER