Number of the records: 1
Core-based criterion for extreme supermodular functions
- 1.0459059 - ÚTIA 2017 RIV NL eng J - Journal Article
Studený, Milan - Kroupa, Tomáš
Core-based criterion for extreme supermodular functions.
Discrete Applied Mathematics. Roč. 206, č. 1 (2016), s. 122-151. ISSN 0166-218X. E-ISSN 1872-6771
R&D Projects: GA ČR GA13-20012S
EU Projects: European Commission 622645 - OASIG
Institutional support: RVO:67985556
Keywords : supermodular function * submodular function * core * conditional independence * generalized permutohedron * indecomposable polytope
Subject RIV: BA - General Mathematics
Impact factor: 0.956, year: 2016
http://library.utia.cas.cz/separaty/2016/MTR/studeny-0459059.pdf
We give a necessary and sufficient condition for extremality of a supermodular function based on its min-representation by means of (vertices of) the corresponding core polytope. The condition leads to solving a certain simple linear equation system determined by the combinatorial core structure. This result allows us to characterize indecomposability in the class of generalized permutohedra. We provide an in-depth comparison between our result and the description of extremality in the supermodular/submodular cone achieved by other researchers.
Permanent Link: http://hdl.handle.net/11104/0259703
Number of the records: 1