Advanced Search

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

Citations: Zbl 0794.05077; Zbl 1102.90053; Zbl 1083.05032; Zbl 1072.05026; Zbl 1112.05082

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]