PROCEEDINGS IPMU '08

On the polytope of fuzzy measures

Elías F. Combarro, P. Miranda.

In this paper we deal with the problem
of studying some mathematical
aspects regarding the polytope
of fuzzy measures when the referential
set is finite. More concretely, we
study whether two extreme points
are adjacent; for general polytopes,
this is a NP-hard problem. However,
for the case of fuzzy measures, we
give a necessary and sufficient condition
for two extreme points to be adjacent.
This allows us to prove that
it is possible to find out in polynomial
time (in the number of minimal
subsets) whether two extremes
are adjacent. These results can be
extended to the polytope given by
the convex hull of monotone boolean
functions.

PDF full paper |