Limitations of the Hyperplane Separation Technique for Bounding the Extension Complexity of Polytopes

11/05/2019
by   Matthias Brugger, et al.
0

This note illustrates the limitations of the hyperplane separation bound, a non-combinatorial lower bound on the extension complexity of a polytope. Most notably, this bounding technique is used by Rothvoß (J ACM 64.6:41, 2017) to establish an exponential lower bound for the perfect matching polytope. We point out that the technique is sensitive to the particular choice of slack matrix. For the canonical slack matrices of the spanning tree polytope and the completion time polytope, we show that the lower bounds produced by the hyperplane separation method are trivial.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset