2019/11/04 by Matthias Brugger, Brugger, Matthias
Computer Science · Engineering · #52Bxx #90Cxx #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1911.01541
openalex publication_date 2019/11/04 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We illustrate the limitations of the hyperplane separation bound, a\nnon-combinatorial lower bound on the extension complexity of a polytope. Most\nnotably, this bounding technique is used by Rothvo ss (J ACM 64.6:41, 2017)\nto establish an exponential lower bound for the perfect matching polytope. We\npoint out that the technique is sensitive to the particular choice of slack\nmatrix. For the canonical slack matrices of the spanning tree polytope and the\ncompletion time polytope, we show that the lower bounds produced by the\nhyperplane separation method are trivial. These bounds may, however, be\nstrengthened by normalizing rows and columns of the slack matrices.\n