On the behavior of the N+-operator under blocker duality

BIANCHI, SILVIA MARIA; ESCALANTE MARIANA SILVINA; NASINI GRACIELA LEONOR

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam ; Año: 2011 vol. 159 p. 396 - 399

0166-218X

In this work we consider the Lovász and Schrijver N+-rank (Lovász and Schrijver, 1991) of set covering polytopes. In particular, we prove that given any positive integer number k there is a 0, 1 matrix for which the N+-rank of its set covering polyhedron and the N+-rank of the set covering polyhedron of its blocker differ by at least k. This shows the contrast between the behavior of the N+ procedure and the disjunctive procedure observed in Aguilera et al.  (2002).