2010-04-01
Polyhedra with the integer Caratheodory property
Publication
Publication
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 | |
---|---|
, , , , | |
Cornell University Library | |
arXiv.org e-Print archive | |
Organisation | Networks and Optimization |
Gijswijt, D., & Regts, G. (2010). Polyhedra with the integer Caratheodory property. arXiv.org e-Print archive. Cornell University Library . |