Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1203.90127
Argiroffo, Gabriela R.; Bianchi, Silvia M.
On the set covering polyhedron of circulant matrices.
(English)
[J] Discrete Optim. 6, No. 2, 162-173 (2009). ISSN 1572-5286

Summary: A well known family of minimally nonideal matrices is the family of the incidence matrices of chordless odd cycles. A natural generalization of these matrices is given by the family of circulant matrices. Ideal and minimally nonideal circulant matrices have been completely identified by {\it G. Cornuéjols} and {\it B. Novick} [J. Comb. Theory, Ser. B 60, No.\,1, 145--147 (1994; Zbl 0794.05077)]. In this work we classify circulant matrices and their blockers in terms of the inequalities involved in their set covering polyhedra. We exploit the results due to Cornuéjols and Novick in the above-cited reference for describing the set covering polyhedron of blockers of circulant matrices. Finally, we point out that the results found on circulant matrices and their blockers present a remarkable analogy with a similar analysis of webs and antiwebs due to {\it A. Pêcher} and {\it A. K. Wagler} [Eur. J. Comb. 27, No.\,7, 1172--1185 (2006; Zbl 1102.90053); Math. Program. 105, 311--328 (2006; Zbl 1083.05032)] and {\it A. K. Wagler} [in: The sharpest cut. Impact of Manfred Padberg and his work, in: MPS/SIAM Series on Optimization 4, 77--96 (2004; Zbl 1072.05026); 4OR 2, No.\,2, 149--152 (2004; Zbl 1112.05082)].
MSC 2000:
*90C27 Combinatorial programming
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
15B57
05B20 (0,1)-matrices (combinatorics)
05C50 Graphs and matrices
05C17 Perfect graphs

Keywords: set covering polyhedron; circulant matrix; fractional extreme point; non-Boolean facet

Highlights
Master Server