Article ID Journal Published Year Pages File Type
419219 Discrete Applied Mathematics 2016 9 Pages PDF
Abstract

We study the set covering polyhedron related to circulant matrices. In particular, our goal is to characterize the first Chvátal 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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,