Answers are grounded in this paper and cite their sources.
When dealing with a fuzzy measure on <tex-math notation="LaTeX">n</tex-math> elements, verifying satisfaction of the monotonicity conditions typically requires performing <tex-math notation="LaTeX">n2ⁿ⁻¹</tex-math> comparisons on measure values, while checking the convexity conditions involves <tex-math notation="LaTeX">n2 2ⁿ⁻²</tex-math> comparisons among marginal contributions. The exponential computation required for these checks in fuzzy measure optimization models often leads heuristic algorithms into numerous challenging situations. In this contribution, we propose efficient comparison algorithms based on sorting methods, linear extensions of fuzzy measures, and partial orders on set pairs of marginal contributions. With the aid of these algorithms, the computational complexity is substantially reduced to a linear level on average. Our numerical experiments confirm the significant benefit when it comes to scenarios with large values of <tex-math notation="LaTeX">n</tex-math>, (e.g., <tex-math notation="LaTeX">$n>10$</tex-math>), allowing us to apply these methods to problems that were previously intractable.
No takes yet. Share an insight, caveat, or question.
Beliakov et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: