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.

, , , ,
Cornell University Library
arXiv.org e-Print archive
Networks and Optimization

Gijswijt, D., & Regts, G. (2010). Polyhedra with the integer Caratheodory property. arXiv.org e-Print archive. Cornell University Library .