A comparison between lift-and-project indices and imperfection ratio on web graphs.

BIANCHI, SILVIA MARIA; ESCALANTE MARIANA SILVINA; MONTELAR, MARÍA SUSANA

Simposio; 2010 (International Symposium in Combinatorial Optimization); 2010

In this paper we study the lift-and-project polyhedral operators defined by Lovász and Schrijver and by Balas, Ceria and Cornuéjols on the clique relaxation of the stable set polytope of webs. We prove they have the same perfomance when starting from the clique relaxation of the family of webs W^k_{s(k+1)+k}. Considering the lift-and-project strength of facets for the stable set polytope on webs, we obtain that the facets of maximum strength for the family W^k_{s(k+1)+k} are also the facets of maximum strength according to Goemans’ measure. This last result is obtained by means of the imperfection index and imperfection ratio.