A polyhedron $P$ has the Integer Carath\'eodory Property if the following holds. For any positive integer $k$ and any integer vector $w$ in $kP$, there exist affinely independent integer vectors $x_1,\ldots,x_t$ in $P$ and positive integers $n_1,\ldots,n_t$ such that $n_1+\cdots+n_t=k$ and $w=n_1x_1+\cdots+n_tx_t$. In this paper we prove that if $P$ is a (poly)matroid base polytope or if $P$ is defined by a TU matrix, then $P$ and projections of $P$ satisfy the integer Carath\'eodory property.

Additional Metadata
Keywords Caratheodory, matroid, base polytope, TU matrix, integer decomposition
MSC Integer programming (msc 90C10)
THEME Logistics (theme 3)
Publisher Cornell University Library
Series arXiv.org e-Print archive
Note 12 pages
Citation
Gijswijt, D, & Regts, G. (2010). Polyhedra with the integer Caratheodory property. arXiv.org e-Print archive. Cornell University Library .