The nonidealness index of rank-ideal matrices |
| |
Authors: | Gabriela R. Argiroffo Silvia M. Bianchi |
| |
Affiliation: | Depto. de Matemática- Facultad de Ciencias Exactas, Ingeniería y Agrimensura- Universidad Nacional de Rosario. Av. Pellegrini 250, 2000 Rosario, Argentina |
| |
Abstract: | A polyhedron is integral if all its extreme points have 0, 1 components and in this case the matrix M is called ideal. When Q has fractional extreme points, there are different ways of classifying how far M is away from being ideal, through the polyhedral structure of Q. In this sense, Argiroffo, Bianchi and Nasini (2006) [1] defined a nonidealness index analogous to an imperfection index due to Gerke and McDiarmid (2001) [10].In this work we determine the nonidealness index of rank-ideal matrices (introduced by the authors (2008)). It is known that evaluating this index is NP-hard for any matrix. We provide a tractable way of evaluating it for most circulant matrices, whose blockers are a particular class of rank-ideal matrices, thereby following similar lines as done for the imperfection ratio of webs due to Coulonges, Pêcher and Wagler (2009) [7].Finally, exploiting the properties of this nonidealness index, we identify the facets of the set covering polyhedron of circulant matrices, having maximum strength with respect to the linear relaxation, according to a measure defined by Goemans (1995) [9]. |
| |
Keywords: | Set covering polyhedron Nonideal matrix Nonidealness index Circulant matrix |
本文献已被 ScienceDirect 等数据库收录! |
|