Abstract:
The relation between submodular functions and functions which dictate the extreme properties of monotone systems proves that on a chain of an arbitrary set-theoretic interval the submodular function varies slower than the linear function of the cardinality of sets that are ranked along it; branch-and-bound algorithms are developed for its unconditions and conditional maximization with an optimal tree-tracing path. With reference to typical problems in aggregation of empirical information it is shown that the solution can be obtained by using the well-developed technique of combinatorial optimization of submodular functions.