Strength of facets for the set covering and set packing polyhedra on circulant matrices

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

Electronic Notes in Discrete Mathematics

Elsevier

Lugar: The Netherlands; Año: 2009 vol. 35 p. 109 - 114

1571-0653

In this paper we prove that the N+-rank coincides with the disjunctive and N-rankfor the linear relaxation of the set covering polyhedron of the circulant matricesC^k_{sk+1} and C^k_{sk} if s ≥ k + 1. We analyze the behavior of the same operators onthe clique relaxation of the stable set polytope of W^2_n with n ≥ 6, which has beencompletely described by Dahl. We define the strength of the facets with respectto the linear relaxation of the set packing and set covering polyhedra, according tothese operators and compare the results with Goemans’ measure.