Core-based criterion for extreme supermodular functions
From MaRDI portal
Abstract: 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. Our 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 6009887 (Why is no real title available?)
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 48344 (Why is no real title available?)
- scientific article; zbMATH DE number 3470175 (Why is no real title available?)
- scientific article; zbMATH DE number 2150792 (Why is no real title available?)
- scientific article; zbMATH DE number 1857870 (Why is no real title available?)
- scientific article; zbMATH DE number 3204690 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- scientific article; zbMATH DE number 3106184 (Why is no real title available?)
- A class of extreme convex set functions with finite carrier
- A generalization of the Shapley-ichiishi result
- Characterizing convexity of games using marginal vectors
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Cones of elementary imsets and supermodular functions: a review and some new results
- Convex Polytopes
- Cores of convex games
- Cores of cooperative games, superdifferentials of functions, and the Minkowski difference of sets
- Cores of exact games. I
- Efficient algorithms for conditional independence inference
- Extremality of submodular functions
- Extreme convex set functions with finite carrier: General theory
- Extreme lower previsions
- Extreme lower probabilities
- Faces of generalized permutohedra
- Indecomposable Polytopes
- Matroid polytopes and their volumes
- On open questions in the geometric approach to structural learning Bayesian nets
- Permutohedra, Associahedra, and Beyond
- Polyhedral aspects of score equivalence in Bayesian network structure learning
- Semimodular Functions and Combinatorial Geometries
- Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion
- Submodular functions and optimization
- Super-modularity: Applications to convex games and to the greedy algorithm for LP
- Supermodular functions on finite lattices
- The expressive power of binary submodular functions
Cited in
(13)- Linear criterion for testing the extremity of an exact game based on its finest min-representation
- Coxeter submodular functions and deformations of Coxeter permutahedra
- Algebraic structures in statistical methodology. Abstracts from the workshop held December 4--10, 2022
- The cone of supermodular games on finite distributive lattices
- Remarkable polyhedra related to set functions, games and capacities
- Polyhedral aspects of score equivalence in Bayesian network structure learning
- The intermediate set and limiting superdifferential for coalitional games: between the core and the Weber set
- Self-adhesivity in lattices of abstract conditional independence models
- Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity
- Polyhedral approaches to learning Bayesian networks
- Equivalence of permutation polytopes corresponding to strictly supermodular functions
- Supermodularity in mean-partition problems
- Facets of the cone of exact games
This page was built for publication: Core-based criterion for extreme supermodular functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q277638)
