I. B. Muchnik and L. V. Shvartser

Submodular Set Functions and Monotone Systems in Aggregation. I,II

Summary I. (pdf-I) A relationship is established between two types of set functions - submodular functions and functions determining the extremal properties of monotone systems. It is shown that this relationship may be utilized in applied combinatorial optimization problems, in particular, for identifying the structure of empirical information.

Summary II. (pdf-II) The relationship from Part I between submodular functions and functions determining the extremal properties of monotone systems is applied to prove that, on the chain of any set-theoretical interval, the submodular function varies more slowly than the linear function of the cardinality of ordered sets. Branch-and-bound algorithms are developed for unconstrained and constrained extremization with optimal tree traversal. Some standard examples of aggregation of empirical data are solved by applying the apparatus of combinatorial optimization of submodular functions.