A characterization of box-mengerian matroid ports

Abstract

Let M be a matroid on E ∪ {l}, where l ∉ E is a distinguished element of M. The l-port of M is the set P = {P: P ⊆ E with P ∪ {l} a circuit of M }. Let A be the P-E incidence matrix. Let U2,4 be the uniform matroid on four elements of rank two, let F7 be the Fano matroid, let F*7 be the dual of F7, and let F 7 + 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 F*7-minor using l, and no F7 +-minor using l as a series element. Our characterization yields a number of interesting results in combinatorial optimization. © 2008 INFORMS.