Ústav teorie informace a automatizace

Jste zde

Bibliografie

Journal Article

Core-based criterion for extreme supermodular functions

Studený Milan, Kroupa Tomáš

: Discrete Applied Mathematics vol.206, 1 (2016), p. 122-151

: GA13-20012S, GA ČR, 622645, EC

: supermodular function, submodular function, core, conditional independence, generalized permutohedron, indecomposable polytope

: 10.1016/j.dam.2016.01.019

: http://library.utia.cas.cz/separaty/2016/MTR/studeny-0459059.pdf

(eng): 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.

: BA

07.01.2019 - 08:39