On vertex denominators of the Boolean quadric polytope relaxation
Andrei V. Nikolaev · Applied Mathematical Sciences · 2015
We study the Mn and Mn,3 relaxations of the boolean quadric polytope BQPn. Corresponding via the covariance mapping cut polytope relaxations are known as the rooted semimetric and metric polytopes. A sequence of Mn,3 fractional vertices, generated by triangle inequalities, is constructed with the largest denominator growing exponentially in n. This refutes the previously conjectured linear upper bound for this value. Mathematics Subject Classification: 52B12, 90C57