数学
马尔可夫链
多面体
单调函数
集合(抽象数据类型)
格子(音乐)
离散数学
马尔可夫决策过程
算法
组合数学
数学优化
马尔可夫过程
计算机科学
数学分析
统计
物理
声学
程序设计语言
作者
Michel Grabisch,Christophe Labreuche,Peiqi Sun
出处
期刊:Order
[Springer Nature]
日期:2023-05-02
被引量:5
标识
DOI:10.1007/s11083-023-09630-0
摘要
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.
科研通智能强力驱动
Strongly Powered by AbleSci AI