Eine Min-Max Beziehung für das Exakte Matroid Problem. (A min-max relation for the exact matroid problem) (Q1084400)

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.