SIMULATION OF BEHAVIOR AND INTELLIGENCE |

Moscow. Translated from Avtomatika and Telemekhanika, No. 5, pp. 135-148, May 1987, I , Original Article submitted June 2, 1986; No. 6, pp. 138-137, June, 1987, II,Original Article submitted June 4, 1986. |

UDC 62-506.1 |

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.