Eastern Great Lakes Theory Workshop Talk

0/1 Polytopes with Quadratic Chvátal Rank

Laura Sanità, University of Waterloo

Sunday, September 30, 10:30am-11:30am

ABSTRACT

For a polytope P, the Chvátal closure is obtained by simultaneously strengthening all feasible inequalities $cx \leq b$ (with integral c) to $cx \leq \lfloor b \rfloor$. The number of iterations of this procedure that are needed until the integral hull of P is reached is called the Chvátal rank. If P is contained in the 0/1 cube, then it is known that O(n^2 \log n) iterations always suffices (Eisenbrand and Schulz (1999)) and at least (1+\frac{1}{e}-o(1))n iterations are sometimes needed (Pokutta and Stauffer (2011)), leaving a huge gap between lower and upper bounds. We prove that there is a polytope contained in the 0/1 cube that has Chvátal rank $\Omega(n^2)$, closing the gap up to a logarithmic factor. In fact, even a superlinear lower bound was mentioned as an open problem by numerous authors.

Joint work with Thomas Rothvoss (MIT).

Speaker Bio

Laura Sanità got a Ph.D. in Operation Research in 2009 from Università Sapienza di Roma. Subsequently, she was a postodoctoral researcher at the Institute of Mathematics of the Ecole Polytechnique Fédérale de Lausanne (Switzerland) from 2009 to 2011. Currently, she is an Assistant Professor in the Department of Combinatorics & Optimization of the Faculty of Mathematics at the University of Waterloo.

Laura has a broad research interest in mathematical problems originating from the areas of combinatorial optimization and operations research. In particular, her main field of expertise is the design, analysis and experimental evaluation of algorithms for network optimization problems.

< Schedule < EaGL-IV homepage