Core-based criterion for extreme supermodular functions

0459059 - ÚTIA 2017 RIV NL eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GA13-20012S
GRANT EU: European Commission 622645 - OASIG
Institucionální podpora: RVO:67985556
Klíčová slova: supermodular function * submodular function * core * conditional independence * generalized permutohedron * indecomposable polytope
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.956, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0259703