Some advances on the set covering polyhedron of circulant matrices

DOI10.1016/J.DAM.2013.10.005MaRDI QIDQ2636828zbMATH OpenOpenAlexFDO

Authors Silvia M. Bianchi, G. Nasini, P. Tolomei

Publication date 18 February 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.6142

zbMATH Keywords

circulant matrixseparation routinesset covering polyhedron

Mathematics Subject Classification ID

Hermitian, skew-Hermitian, and related matrices (15B57) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Abstract: Working on the set covering polyhedron of consecutive ones circulant matrices, Argiroffo and Bianchi found a class of facet defining inequalities, induced by a particular family of circulant minors. In this work we extend these results to inequalities associated with every circulant minor. We also obtain polynomial separation algorithms for particular classes of such inequalities.

Recommendations

• The minor inequalities in the description of the set covering polyhedron of circulant matrices
• Generalized minor inequalities for the set covering polyhedron related to circulant matrices
• Strength of facets for the set covering and set packing polyhedra on circulant matrices
• Minor related row family inequalities for the set covering polyhedron of circulant matrices
• On the set covering polyhedron of circulant matrices

Cites work

• A class of facet producing graphs for vertex packing polyhedra
• A linear algorithm for finding a minimum dominating set in a cactus
• A linear algorithm for the domination number of a series-parallel graph
• Dominating sets for split and bipartite graphs
• Dominating sets in perfect graphs
• Domination on Cocomparability Graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Facets and lifting procedures for the set covering polytope
• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 1302196 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Ideal 0, 1 matrices
• Notes on ``Ideal 0, 1 matrices by Cornuéjols and Novick
• On a routing problem
• On packing and covering polyhedra of consecutive ones circulant clutters
• On the dominating set polytope
• On the dominating set polytope of web graphs
• On the facial structure of the set covering polytope
• On the set covering polyhedron of circulant matrices

Cited in

(13)

• On the set covering polyhedron of circulant matrices
• On the 0,1 facets of the set covering polytope
• Lift-and-project ranks of the set covering polytope of circulant matrices
• The minor inequalities in the description of the set covering polyhedron of circulant matrices
• On dominating set polyhedra of circular interval graphs
• Strength of facets for the set covering and set packing polyhedra on circulant matrices
• On the dominating set polytope of web graphs
• The set covering problem on circulant matrices: polynomial instances and the relation with the dominating set problem on webs
• Generalized minor inequalities for the set covering polyhedron related to circulant matrices
• Minor related row family inequalities for the set covering polyhedron of circulant matrices
• Arithmetic relations in the set covering polyhedron of circulant clutters
• The nonidealness index of circulant matrices
• Vertex adjacencies in the set covering polyhedron

This page was built for publication: Some advances on the set covering polyhedron of circulant matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2636828)