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
    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

    Identifiers