Una perspectiva algebraica al problema de recubrimiento en matrices circulantes

Abstract

En el presente trabajo se estudiarán algunas propiedades algebraicas de las matrices circulantes, y su relación con el poliedro de recubrimiento. Se caracterizan las inversas de la clase particular de las matrices circulantes con coeficientes en {0, 1} y se emplean estos resultados para obtener una nueva familia de desigualdades válidas para el poliedro de recubrimiento asociado a ellas. Por otra parte, se presentan algoritmos polinomiales para la solución del problema de recubrimiento asociado a matrices circulantes con coeficientes en {0, 1} así como para la separación de una clase específica de desigualdades.