Minization and Maximization of Quasi-Supermodular Functions
DOI:
https://doi.org/10.17268/sel.mat.2018.02.07Keywords:
Combinatorial optimization, quasi-supermodular function, supermodular function, finite lattice, boolean latticeAbstract
This article presents some properties of the casisupermodular function and demonstrates principles of discarding to solve the problem of minimization and maximization of this type of function defined in the family of subsets of a given finite set (finite boolean lattice); these principles are generalized, in the case of minimization, to a relatively complemented finite lattice. This work extends some results obtained by V.R. Khachaturov and R.V. Khachaturov for the case of supermodular functions.
References
Aragonés Salazar, N. O. Minimización de Funciones Supermodulares, Selecciones Matemáticas. Vol 02(02): 49-52 (2015).
Aragonés Salazar, N.O. Minimización de Funciones Supermodulares en un retículo finito relativamente complementado, Selecciones Matemáticas. Vol 04(02): 175-176 (2017).
Grätzer, G. LATTICE THEORY. First concepts and distributive lattices, Dover Publications, INC. Mineola, New York. (1970).
Jachatúrov, R.V. Algoritmos de maximización de funciones supermodulares y su aplicación en la optimización del agrupamiento de zonas de una región, Revista de matemática computacional y física matemática. T.39, Nž1, 33-44 (1999).
Khachaturov, V. R., Lorer, V.E. Investigación y minimización de funciones supermodulares en retículos atómicos. Communications on applied mathematics. Dorodnicyn Computing Centre of RAS, 1987. 41 p.
Jachatúrov, V. R. Métodos matemáticos de programación regional, Nauka, Moscú, Rusia. (1989).
Khachaturov, V. R., Montlevich, V.M. Minimización de funciones supermodulares en retículos distributivos // Communications on applied mathematics. Dorodnicyn Computing Centre of RAS, 1999. 49 p.
Jachatúrov, V. R. Métodos Combinatorios y Algoritmos para la solución de problemas de optimización discreta de gran escala, Nauka, Moscú, Rusia. (2000).
Khachaturov, V.R., Khachaturov, R.V. Supermodular programming on Lattices. Comput. Sci. J. Moldova. 2003. V. 11. No 1(31). P. 4372.
Mei, J., Zhao, K., Lu, B. Unconstrained Quasi-Submodular Function Optimization, Proceeding AAAI’15 Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. (2015) 1191-1197.
Roman, S. Lattices and Ordered Sets. Springer-Verlag, New York, 2008.
Published
How to Cite
Issue
Section
License
The authors who publish in this journal accept the following conditions:
1. The authors retain the copyright and assign to the journal the right of the first publication, with the work registered with the Creative Commons Attribution License,Atribución 4.0 Internacional (CC BY 4.0) which allows third parties to use what is published whenever they mention the authorship of the work And to the first publication in this magazine.
2. Authors may make other independent and additional contractual arrangements for non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly state that The paper was first published in this journal.
3. Authors are encouraged to publish their work on the Internet (for example, on institutional or personal pages) before and during the review and publication process, as it can lead to productive exchanges and to a greater and more rapid dissemination Of the published work.
