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

DOI10.1016/J.DAM.2015.06.034zbMATH Open1339.05378arXiv1406.4560OpenAlexW1535343312MaRDI QIDQ299092FDOQ299092

Authors: P. Tolomei, Luis M. Torres 

Publication date: 22 June 2016

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

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.

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

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

zbMATH Keywords

circulant matricesset covering[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Chv%EF%BF%BD%EF%BF%BDtal+closure&go=Go Chv��tal closure]

Mathematics Subject Classification ID

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

Cites Work

• On the set covering polyhedron of circulant matrices
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the 0,1 facets of the set covering polytope
• On the facial structure of the set covering polytope
• Facets and lifting procedures for the set covering polytope
• Ideal 0, 1 matrices
• On the dominating set polytope
• The minor inequalities in the description of 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
• Title not available (Why is that?)
• The stable set polytope of quasi-line graphs
• On packing and covering polyhedra of consecutive ones circulant clutters

Cited In (7)

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