University of Washington
An important concern in discrete optimization is to understand the facets of the convex hull of integer points (integer hull) of a rational polyhedron. A well-known measure of the complexity of the integer hull of a polyhedron is the Chvatal rank of the polyhedron. We introduce a new measure of complexity of integer hulls called the small Chvatal rank (SCR) which is bounded above by Chvatal rank. The difference can be surprisingly large in some examples although both ranks have the same asymptotic behavior in general. For instance, the SCR of the stable set polytope of a perfect graph is two while Chvatal rank is known to be O(log n) where n is the number of vertices in the graph. We characterize the situation when SCR equals zero.
Joint work with Tristram Bogart & Annie Raymond.
University of Washington