An approximation algorithm for random generation of capacities. (English) Zbl 07922992
Summary: 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.
MSC:
| 06-XX | Order, lattices, ordered algebraic structures |
References:
| [1] | Beliakov, G., On random generation of supermodular capacities, IEEE Tr. on Fuzzy Systems, 30, 293-296, 2022 · doi:10.1109/TFUZZ.2020.3036699 |
| [2] | Brightwell, G.; Tetali, P., The number of linear extensions of the Boolean lattice, Order, 20, 333-345, 2003 · Zbl 1061.06001 · doi:10.1023/B:ORDE.0000034596.50352.f7 |
| [3] | Brightwell, G.; Winkler, P., Counting linear extensions, Order, 8, 225-242, 1991 · Zbl 0759.06001 · doi:10.1007/BF00383444 |
| [4] | Bubley, R.; Dyer, M., Faster random generation of linear extensions, Discrete Mathematics, 201, 81-88, 1999 · Zbl 0934.65005 · doi:10.1016/S0012-365X(98)00333-1 |
| [5] | Choquet, G., Theory of capacities, Annales de l’Institut Fourier, 5, 131-295, 1953 · Zbl 0064.35101 · doi:10.5802/aif.53 |
| [6] | Combarro, EF; Díaz, I.; Miranda, P., On random generation of fuzzy measures, Fuzzy Sets and Systems, 228, 64-77, 2013 · Zbl 1284.28013 · doi:10.1016/j.fss.2012.09.006 |
| [7] | Combarro, EF; Hurtado de Saracho, J.; Díaz, I., Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets, Information Sciences, 501, 50-67, 2019 · Zbl 1453.06001 · doi:10.1016/j.ins.2019.05.079 |
| [8] | M. Grabisch. Set Functions, Games and Capacities in Decision Making, volume 46 of Theory and Decision Library C. Springer, 2016 · Zbl 1339.91003 |
| [9] | T. C. Havens and A. J. Pinar. Generating random fuzzy (capacity) measures for datafusion simulations. In IEEE Symposium Series on Computational Intelligence (IEEE SSCI2017), pages 1-8, 2017 |
| [10] | Karzanov, A.; Khachiyan, L., On the conductance of order Markov chains, Order, 8, 7-15, 1991 · Zbl 0736.06002 · doi:10.1007/BF00385809 |
| [11] | Miranda, P.; Combarro, E., On the structure of some families of fuzzy measures, IEEE Tr. on Fuzzy Systems, 15, 6, 1068-1081, 2007 · doi:10.1109/TFUZZ.2007.895953 |
| [12] | Miranda, P.; García-Segador, P., Bottom-up: a new algorithm to generate random linear extensions of a poset, Order, 36, 437-462, 2019 · Zbl 1468.06001 · doi:10.1007/s11083-018-9476-1 |
| [13] | Miranda, P.; García-Segador, P., Applying Young diagrams to 2-symmetric fuzzy measures with an application to general fuzzy measures, Fuzzy Sets and Systems, 379, 20-36, 2020 · Zbl 1464.28018 · doi:10.1016/j.fss.2019.01.017 |
| [14] | Miranda, P.; García-Segador, P., Combinatorial structure of the polytope of 2-additive measures, IEEE Transactions on Fuzzy Systems, 28, 2864-2874, 2020 · doi:10.1109/TFUZZ.2019.2945243 |
| [15] | Stanley, R., Two poset polytopes, Discrete and Computational Geometry, 1, 9-23, 1986 · Zbl 0595.52008 · doi:10.1007/BF02187680 |
| [16] | M. Sugeno. Theory of fuzzy integrals and its applications. PhD thesis, Tokyo Institute of Technology, 1974 |
| [17] | T. Talvitie, T. Niinimäki, and M. Koivisto. The mixing of Markov chains on linear extensions in practice. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17), pages 524-530, Melbourne, Australia, 2017 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
