论文标题
一种随机生成能力的近似算法
An approximation algorithm for random generation of capacities
论文作者
论文摘要
有限套件上的容量是集合在空集上消失的功能，并且是单调的W.R.T.包容。由于一组能力是一个阶级多层，因此随机产生能力的问题等于生成布尔晶格的所有线性扩展。已知该问题即使在$ n> 5 $的情况下也很棘手，因此已经提出了近似方法，最著名的是基于马尔可夫链的方法。尽管非常准确，但这种方法很耗时。在本文中，我们提出了2层近似方法，该方法生成线性扩展的子集，从而消除了概率非常低的人。我们表明，与马尔可夫链相比，我们的方法具有相似的性能，但耗时要少得多。
Capacities on a finite set are sets functions vanishing on the empty set and being monotonic w.r.t. inclusion. Since the set of capacities is an order polytope, the problem of randomly generating capacities amounts to generating all linear extensions of the Boolean lattice. This problem is known to be intractable even as soon as $n>5$, therefore approximate methods have been proposed, most notably one based on Markov chains. Although quite accurate, this method is time consuming. In this paper, we propose the 2-layer approximation method, which generates a subset of linear extensions, eliminating those with very low probability. We show that our method has similar performance compared to the Markov chain but is much less time consuming.
