2012
Polyhedra with the integer Caratheodory property
Publication
Publication
Journal of Combinatorial Theory - Series B , Volume 102 - Issue 1 p. 62- 70
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 | |
---|---|
, , , , | |
Academic Press | |
Journal of Combinatorial Theory - Series B | |
Organisation | Networks and Optimization |
Gijswijt, D., & Regts, G. (2012). Polyhedra with the integer Caratheodory property. Journal of Combinatorial Theory - Series B, 102(1), 62–70. |