|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Max Product for Max-Weight Independent Set and Matching | | Devavrat Shah
; | | Date: |
23 Aug 2005 | | Subject: | Data Structures and Algorithms; Discrete Mathematics | cs.DS cs.DM | | Abstract: | The Max Product (MP) is a local, iterative, message passing style algorithm that has been developed for finding the maximum a posteriori (MAP) assignment of discrete probability distribution specified by a graphical model. The scope of application of MP is vast and in particular it can serve as a heuristic to solve any combinatorial optimization problem. Despite the success of MP algorithm in the context of coding and vision, not much has been theoretically understood about the correctness and convergence of MP. The Maximum Weight Independent Set (MWIS) and Maximum Weight Matching (MWM) are classically well studied combinatorial optimization problems. A lot of work has been done to design efficient algorithms for finding MWIS and MWM. In this paper, we study application of MP algorithm for MWIS and MWM for sparse random graphs: $G(n,c/n)$ and $G_r(n)$, which are $n$ node random graphs with parameter $c$ and $r$ respectively. We show that when weights (node or edge depending on MWIS or MWM) are assigned independently according to exponential distribution, the MP algorithm converges and finds correct solution for a large range of parametric value $c$ and $r$. In particular, we show that for any $epsilon > 0$, for large enough $n$, the MP becomes $1+epsilon$ competitive with probability at least $1-epsilon$. Our results build upon the results of Gamarnik, Nowicki and Swirscsz (2005), which established emph{local optimality property} of MWIS and MWM for sparse random graphs. | | Source: | arXiv, cs.DS/0508097 | | 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