M. Studeny, R.R. Bouckaert, T. Kocka:
Extreme supermodular set functions over five variables.
Research report n. 1977,
Institute of Information Theory and Automation,
Prague, January 2000. (32 pages)
- Abstract
- The class of supermodular functions on the power set
of a non-empty finite set N forms a cone. It can be viewed
as the direct sum of a linear subspace and of a cone of standardized
supermodular functions which has finitely many extreme rays.
Every extreme ray can be described by a standardized integer-valued
set function. The situation in the case when N has five
elements (variables) is analysed. A computer program was used
to obtain a catalogue of all classes of permutably equivalent
extreme standardized supermodular functions on the power set
of N. Several alternative ways of representation of these
equivalence classes are considered and various characteristics
are used to describe them. Moreover, two relevant hypotheses valid
in case of four variables are disproved in case of five
variables.
- AMS classification 68T30 90D99 52B99
- Keywords
- extreme supermodular set function
- permutably equivalent functions
- imset
- cone
-
A
pdf version (265kB) is available.
-
Moreover, the result of the work is also an
electronic catalogue of representatives extreme supermodular set functions over five variables.