zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
On the set covering polyhedron of circulant matrices. (English) Zbl 1203.90127
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)].

90C27Combinatorial optimization
52B12Special polytopes (linear programming, centrally symmetric, etc.)
15B57Hermitian, skew-Hermitian, and related matrices
05B20Matrices (incidence, Hadamard, etc.)
05C50Graphs and linear algebra
05C17Perfect graphs
Full Text: DOI
[1] G. Argiroffo, Clasificación de clutters no ideales, Ph.D. Dissertation, Universidad Nacional de Rosario, Argentina, 2005
[2] Argiroffo, G. R.; Bianchi, S. M.; Nasini, G. L.: On a certain class of nonideal clutters, Discrete applied mathematics 154, 1854-1864 (2006) · Zbl 1097.05012 · doi:10.1016/j.dam.2006.03.027
[3] Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R.: The strong perfect graph theorem, Annals of mathematics 164, 51-229 (2006) · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51
[4] Chvátal, V.: On certain polytopes associated with graphs, Journal of combinatorial theory series (B) 18, 138-154 (1975) · Zbl 0277.05139 · doi:10.1016/0095-8956(75)90041-6
[5] Cornuéjols, G.: Combinatorial optimization: packing and covering, Cbms 74 (2001) · Zbl 0972.90059 · doi:10.1137/1.9780898717105
[6] Cornuéjols, G.; Novick, B.: Ideal 0-1 matrices, Journal of combinatorial theory series B 60, 145-157 (1994) · Zbl 0794.05077 · doi:10.1006/jctb.1994.1009
[7] Fulkerson, D.: Blocking polyhedra, Graph theory and its applications, 93-112 (1970) · Zbl 0217.18505
[8] Lehman, A.: On the width--length inequality, Mathematical programming 17, 403-417 (1979) · Zbl 0418.90040 · doi:10.1007/BF01588263
[9] Lehman, A.: On the width--length inequality and degenerate projective planes, DIMACS series in discrete math. And theoretical computer science 1, 101-105 (1990) · Zbl 0747.05063
[10] Nobili, P.; Sassano, A.: Facets and lifting procedures for the set covering polytope, Mathematical programming 45, 111-137 (1989) · Zbl 0677.90055 · doi:10.1007/BF01589100
[11] Padberg, M. W.: Almost integral polyhedra related to certain combinatorial optimization problems, Linear algebra and its applications 15, 339-342 (1976) · Zbl 0362.90077 · doi:10.1016/0024-3795(76)90079-3
[12] Padberg, M. W.: Lehman’s forbidden minor characterization of ideal 0-1 matrices, Discrete mathematics 11, 409-420 (1993) · Zbl 0798.05010 · doi:10.1016/0012-365X(93)90178-V
[13] Pêcher, A.; Wagler, A.: A construction for non-rank facets of stable set polytopes of webs, European journal of combinatorics 27, 1172-1185 (2006) · Zbl 1102.90053 · doi:10.1016/j.ejc.2006.06.013
[14] Pêcher, A.; Wagler, A.: Almost all webs are not rank-perfect, Mathematical programming series B 105, 311-328 (2006) · Zbl 1083.05032 · doi:10.1007/s10107-005-0655-7
[15] PORTA: www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA
[16] Sassano, A.: On the facial structure of the set covering polytope, Mathematical programming 44, 181-202 (1989) · Zbl 0675.90059 · doi:10.1007/BF01587087
[17] Seymour, P.: The matroids with the MAX-flow MIN-cut property, Journal of combinatorial theory series B 23, 189-222 (1977) · Zbl 0375.05022 · doi:10.1016/0095-8956(77)90031-4
[18] Shepherd, B.: Near-perfect matrices, Mathematical programming 64, 295-323 (1994) · Zbl 0804.05036 · doi:10.1007/BF01582578
[19] Jr., L. E. Trotter: A class of facets producing graphs for vertex packing polyhedra, Discrete mathematics 12, 373-388 (1975) · Zbl 0314.05111 · doi:10.1016/0012-365X(75)90077-1
[20] A. Wagler, Relaxing perfectness: Which graphs are ’Almost’ perfect?, in: M. Groetschel (Ed.), The Sharpest Cut, Impact of Manfred Padberg and his work, in: SIAM/MPS Series on Optimization, vol. 4, Philadelphia, 2004
[21] Wagler, A.: Antiwebs are rank-perfect, 4OR 2, 149-152 (2004) · Zbl 1112.05082 · doi:10.1007/s10288-003-0032-4
[22] A. Wagler, Beyond perfection: On relaxations and superclasses, Habilitation Thesis, Otto-von-Guericke-University Magdeburg, 2007