Eine Min-Max Beziehung für das Exakte Matroid Problem. (A min-max relation for the exact matroid problem) (Q1084400)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Eine Min-Max Beziehung für das Exakte Matroid Problem. (A min-max relation for the exact matroid problem) |
scientific article |
Statements
Eine Min-Max Beziehung für das Exakte Matroid Problem. (A min-max relation for the exact matroid problem) (English)
0 references
1987
0 references
Das Exakte Matroid-Problem ist: Gegeben sei ein Matroid \(M=(E,J)\), eine Teilmenge \(R\subseteq E\) und eine natürliche Zahl \(\ell\); finde eine Basis B von M, so daß \(| B\cap R| =\ell\) gilt. In der Arbeit wird eine Gleichung bewiesen, die das Maximum der R-Elemente in einer Basis in Beziehung zum Minimum der Summe der Ränge einer bestimmten Überdeckung von M setzt. Der Beweis beruht auf einer Charakterisierung des total dual ganzzahligen Systems für das Matroid-Polytop von Edmonds und Giles.
0 references
exact matroid problem
0 references
total dual integral system
0 references
matroid polytope of Edmonds and Giles
0 references