Polyhedra with the Integer Caratheodory Property

Original · EN

A polyhedron P has the Integer Caratheodory Property if the following holds. For any positive integer k and any integer vector w in kP, there exist affinely independent integer vectors x₁,...,xₜ in P and positive integers n₁,...,nₜ such that n₁+...+nₜ=k and w=n₁x₁+...+nₜxₜ. 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 Caratheodory property.