Сет-функция — действительная числовая функция , определенная на  — множестве всех подмножеств некоторого произвольного конечного множества измеримого пространства и принимающая свои значения на числовой оси .

Аддитивная сет-функция — сет-функция, для которой выполняется равенство:

для любых подмножеств и .

Мера — аддитивная сет-функция, для которой верно: .

Значение любой меры на произвольном подмножестве можно представить в виде суммы ее значений на моноплетах :

.

Считается, что .

Библиография

• Lovasz L. (1983) Submodular functions and convexity. In: A. Bachem, M. Grotschel, and B.Korte, editors, Mathematical Programming — The State of the Art}, Springer-Veriag, 235—257.

• Fujishige S. (1984) Theory of submodular programs, A Fenchel-type min-max theorem and subgradients of submodular functions, Mathematical Programming, 29, 142—155.

• Foldes Stephan, Hammer Peter L. (2002) Submodularity, Supermodularity, Higher Order Monotonicities. Rutcor Research

Report, 10-2002, March, 2002.

• Hammer, P.L., and S.Rudeanu} (1968) Boolean Methods in Operation Research and Relared Areas, Springer-Verlag, Berlin, Heidelberg, New York.