A Characterization of Box-Mengerian Matroid Ports

A Characterization of Box-Mengerian Matroid Ports

0.00 Avg rating0 Votes
Article ID: iaor200954172
Country: United States
Volume: 33
Issue: 2
Start Page Number: 497
End Page Number: 512
Publication Date: May 2008
Journal: Mathematics of Operations Research
Authors: , ,
Keywords: matrices, sets
Abstract:

Let M be a matroid on E∪{l}, where lE is a distinguished element of M. The l–port of M is the set 𝒫= {P: PE with P∪{l} a circuit of M}. Let A be the 𝒫–E incidence matrix. Let U2,4 be the uniform matroid on four elements of rank two, let F7 be the Fano matroid, let F7* be the dual of F7, and let F7+ be the unique series extension of F7. In this paper, we prove that the system Ax≥1, x≥0 is box–totally dual integral (box–TDI) if and only if M has no U2,4–minor using l, no F7*–minor using l, and no F7+–minor using l as a series element. Our characterization yields a number of interesting results in combinatorial optimization.

Reviews

Required fields are marked *. Your email address will not be published.