A vector exchange property of submodular systems
From MaRDI portal
The multiple basis exchange property for matroids is generalized as follows, using the sum theorem for submodular systems. If x and y are vectors in a submodular system and \(x=x_ 1+x_ 2\) then there exists \(y_ 1\), \(y_ 2\) such that \(y=y_ 1+y_ 2\) and both \(x_ 1+y_ 1\) and \(x_ 2+y_ 2\) belong to the submodular system. An integral analogue holds for integral submodular systems, and a non-negative analogue for polymatroids.
Recommendations
Cites work
- A Multiple Exchange Property for Bases
- An exchange theorem for bases of matroids
- An Exchange Theorem for Independence Structures
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Some properties of basic families of subsets
- Structures of polyhedra determined by submodular functions on crossing families
- Submodular systems and related topics
Cited in
(5)- Exchange systems
- scientific article; zbMATH DE number 4181354 (Why is no real title available?)
- Lexicographically Optimal Base of a Submodular System with respect to a Weight Vector
- Multiple Exchange Property for M♮-Concave Functions and Valuated Matroids
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
This page was built for publication: A vector exchange property of submodular systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760438)
