RO EN
Supermodular Programming on Lattices
Authors: V.R. Khachaturov, Ro.V. Khachaturov, Ru.V. Khachaturov
The first - elaboration of the basic propositions of the theory of maximization of supermodular functions on Boolean lattices (they were worked out only for the problems of minimization before) and establishing of relation between global minimum and maximum of supermodular function for main types of lattices.
The second - elaboration of original combinatorial algorithms of automatized representation of hyper-cubes (booleans) of large dimension on a plane in the form of various diagrams, on which the properties of boolean as a partially ordered set of its vertexes are kept (This provides us with ample opportunities for construction of various schemes of looking through the elements of atomic lattices and for visualization of the optimization process).
The third - carrying out the basic propositions of the theory of optimization of supermodular functions to the main types of lattices: Boolean lattices, lattices with relative supplements (division lattices, lattices of vector subspaces of finite-dimensional vector space, geometrical spaces), lattices equal to Cartesian product of chains, distributive lattices, atomic lattices.
These theoretical results and availability of the great amount of optimization problems for lattices with concrete forms of supermodular functions allow to consider methods and algorithms for solving the problems of optimization of supermodular functions on lattices as a new field of mathematical programming - supermodular programming [19].
– 0.81 Mb
Abstract
Questions, concerning the optimization of supermodular functions on finite lattices are considered in the paper. The systematic summary of main authors' and other researchers' results known before, new authors' results are given. There should be marked out the following three results among new results.The first - elaboration of the basic propositions of the theory of maximization of supermodular functions on Boolean lattices (they were worked out only for the problems of minimization before) and establishing of relation between global minimum and maximum of supermodular function for main types of lattices.
The second - elaboration of original combinatorial algorithms of automatized representation of hyper-cubes (booleans) of large dimension on a plane in the form of various diagrams, on which the properties of boolean as a partially ordered set of its vertexes are kept (This provides us with ample opportunities for construction of various schemes of looking through the elements of atomic lattices and for visualization of the optimization process).
The third - carrying out the basic propositions of the theory of optimization of supermodular functions to the main types of lattices: Boolean lattices, lattices with relative supplements (division lattices, lattices of vector subspaces of finite-dimensional vector space, geometrical spaces), lattices equal to Cartesian product of chains, distributive lattices, atomic lattices.
These theoretical results and availability of the great amount of optimization problems for lattices with concrete forms of supermodular functions allow to consider methods and algorithms for solving the problems of optimization of supermodular functions on lattices as a new field of mathematical programming - supermodular programming [19].
V.R.Khachaturov, R.V.Khachaturov, R.V.Khachaturov
E-mail:
E-mail:
Fulltext
– 0.81 Mb
Contents
- The splitting method and Poincare's theorem: (II) - matrix, polynomial and language
- On stability of Nash equilibrium situations and Pareto optimal situations in finite games
- Linear-time algorithm for the edge-colorability of a graph with prescribed vertex types
- Supermodular Programming on Lattices
- Fast software-oriented hash function based on data-dependent lookup operations
- About some problems related to collective expertise
- Yurii Nikolaevich Pechersky (a tribute in his memory)
- The jubilee of IM&CS
