Regresar

A lower bound on the Chvátal-rank of Antiwebs

Abstract:

In [Holm, E., L. M. Torres and A. K. Wagler, On the Chvátal-rank of linear relaxations of the stable set polytope, International Transactions in Operational Research 17 (2010), pp. 827-849; Holm, E., L. M. Torres and A. K. Wagler, On the Chvátal-rank of Antiwebs, Electronic Notes in Discrete Mathematics 36 (2010), pp. 183-190] we study the Chvátal-rank of the edge constraint and the clique constraint stable set polytopes related to antiwebs. We present schemes for obtaining both upper and lower bounds. Moreover, we provide an algorithm to compute the exact values of the Chvátal-rank for all antiwebs with up to 5,000 nodes. Here we prove a lower bound as a closed formula and discuss some cases when this bound is tight. © 2011 Elsevier B.V.