Generalized minor inequalities for the set covering polyhedron related to circulant matrices

DOI10.1016/J.DAM.2015.06.034MaRDI QIDQ299092zbMATH OpenOpenAlexFDO

Authors P. Tolomei, Luis M. Torres

Publication date 22 June 2016

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

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

zbMATH Keywords

circulant matricesset coveringChvátal closure

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph minors (05C83)

Abstract: We study the set covering polyhedron related to circulant matrices. In particular, our goal is to characterize the first Chv'atal closure of the usual fractional relaxation. We present a family of valid inequalities that generalizes the family of minor inequalities previously reported in the literature and includes new facet-defining inequalities. Furthermore, we propose a polynomial time separation algorithm for a particular subfamily of these inequalities.

Recommendations

• The minor inequalities in the description of the set covering polyhedron of circulant matrices
• Minor related row family inequalities for the set covering polyhedron of circulant matrices
• On the set covering polyhedron of circulant matrices
• Some advances on the set covering polyhedron of circulant matrices
• Row family inequalities for the set covering polyhedron
• Strength of facets for the set covering and set packing polyhedra on circulant matrices
• Lift-and-project ranks of the set covering polytope of circulant matrices
• Intersection Inequalities for the Covering Problem
• scientific article; zbMATH DE number 1156642
• The generalization of Minkowski problems for polytopes

Cites work

• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• Facets and lifting procedures for the set covering polytope
• Ideal 0, 1 matrices
• On packing and covering polyhedra of consecutive ones circulant clutters
• On the 0,1 facets of the set covering polytope
• On the dominating set polytope
• On the facial structure of the set covering polytope
• On the set covering polyhedron of circulant matrices
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• Row family inequalities for the set covering polyhedron
• Some advances on the set covering polyhedron of circulant matrices
• The minor inequalities in the description of the set covering polyhedron of circulant matrices
• The stable set polytope of quasi-line graphs

Cited in

(9)

• On the dominating set polytope of web graphs
• On the set covering polyhedron of circulant matrices
• Minor related row family inequalities for the set covering polyhedron 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
• Some advances on the set covering polyhedron of circulant matrices
• Arithmetic relations in the set covering polyhedron of circulant clutters
• Lift-and-project ranks of the set covering polytope of circulant matrices
• Strength of facets for the set covering and set packing polyhedra on circulant matrices

This page was built for publication: Generalized minor inequalities for the set covering polyhedron related to circulant matrices

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