Extended Formulations for Radial Cones
share
This paper studies extended formulations for radial cones at vertices of polyhedra, where the radial cone of a polyhedron P at a vertex v ∈ P is the polyhedron defined by the constraints of P that are active at v . Given an extended formulation for P , it is easy to obtain an extended formulation of comparable size for each its radial cones. On the contrary, it is possible that radial cones of P admit much smaller extended formulations than P itself. A prominent example of this type is the perfect-matching polytope, which cannot be described by subexponential-size extended formulations (Rothvoß 2014). However, Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. Moreover, they generalized their construction to V -join polyhedra. In the same paper, the authors asked whether the same holds for the odd-cut polyhedron, the blocker of the V -join polyhedron. We answer this question negatively. Precisely, we show that radial cones of odd-cut polyhedra cannot be described by subexponential-size extended formulations. To obtain our result, for a polyhedron P of blocking type, we establish a general relationship between its radial cones and certain faces of the blocker of P .
READ FULL TEXT