发帖
雷达卡
摘要翻译：
霍岩将计算二部图上所有匹配项的个数转化为计算由扩展二部图得到的矩阵的永久项，Rasmussen提出了一种简单的近似永久项的方法，它只对几乎所有的0-1矩阵产生一个临界比率O($n\omega(n)$)，只要它是一种简单的、有希望的实用方法来计算这个#p-完全问题。在本文中，将该方法应用于计算基于该变换的所有匹配时，将显示该方法的性能。对于几乎所有的0-1矩阵，临界比在一定的概率下都是很大的，甚至在某种意义上，临界比的增加因子大于任何一个n$多项式。因此，当通过计算矩阵的永久值来计算所有匹配时，RM就不能很好地工作。换句话说，我们必须小心地利用估计永久物的已知方法来计算通过那个变换的所有匹配。
---
英文标题：
《An analysis of a random algorithm for estimating all the matchings》
---
作者：
Jinshan Zhang
---
最新提交年份：
2008
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Graphics 图形学
分类描述：Covers all aspects of computer graphics. Roughly includes material in all of ACM Subject Class I.3, except that I.3.5 is is likely to have Computational Geometry as the primary subject area.
涵盖了计算机图形学的各个方面。大致包括所有ACM课程I.3的材料，除了I.3.5可能有计算几何作为主要的学科领域。
--
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
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($n\omega(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.
---
PDF链接：
https://arxiv.org/pdf/0812.1119
京公网安备 11010802022788号
