The N-rank of circulant matrices

BIANCHI, SILVIA MARIA; ESCALANTE MARIANA SILVINA

Buenos Aires-Argentina

Workshop; VI ALIO/EURO Workshop on Applied Combinatorial Optimization; 2008

ALIO

In this paper we analyze the behavior of theN operator (defined by Lov´asz and Schrijver) andthe disjunctive operator due to Balas, Ceria and Cornu´ejols, on the linear relaxation of the set covering polyhedron associated with circulant matrices C^k_n. For most circulant matrices, the complete description of the set covering polyhedron remains unknown. We found the disjunctive rank of circulant matrices of the form C^k_sk and prove that for the family of circulant matrices C^k_sk+1 the disjunctive rank coincides with the N-rank at the value k-1. The circulant matrices C^k_sk+1 appear as minors of many others more general ones, thus providing bounds for their corresponding ranks. For the particular case s = 2, the N+-rank is also k-1.