|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
An analysis of a random algorithm for estimating all the matchings | | Jinshan Zhang
; Yan Huo
; Fengshan Bai
; | | Date: |
12 Nov 2007 | | Abstract: | Counting the number of all the matchings on a bipartite graph has been
transformed into calculating the permanent of a matrix obtained from the
extended bipartite graph by Yan Huo, and Rasmussen presents a simple approach
(RM) to approximate the permanent, which just yields a critical ratio
O($nomega(n)$) for almost all the 0-1 matrices, provided it’s a simple
promising practical way to compute this #P-complete problem. In this paper, the
performance of this method will be shown when it’s applied to compute all the
matchings based on that transformation. The critical ratio will be proved to be
very large with a certain probability, owning an increasing factor larger than
any polynomial of $n$ even in the sense for almost all the 0-1 matrices. Hence,
RM fails to work well when counting all the matchings via computing the
permanent of the matrix. In other words, we must carefully utilize the known
methods of estimating the permanent to count all the matchings through that
transformation. | | Source: | arXiv, 0711.1723 | | 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