We consider the polyhedron Conv{xε{lunate}{0,1}n:Mx≤b}, where M is a p × n matrix of zeroes and ones and b is a nonnegative integer vector. We give a characterization of such polyhedra whose extreme points are the incidence vectors of the family of independent sets of a matroid and extend our result to polyhedra which are the convex hull of integral polymatroids. We also introduce some new classes of integral matroid polyhedra which extend a result of Edmonds. © 1988.
A characterization of matroidal systems of inequalities
CONFORTI, MICHELANGELO;
1988
Abstract
We consider the polyhedron Conv{xε{lunate}{0,1}n:Mx≤b}, where M is a p × n matrix of zeroes and ones and b is a nonnegative integer vector. We give a characterization of such polyhedra whose extreme points are the incidence vectors of the family of independent sets of a matroid and extend our result to polyhedra which are the convex hull of integral polymatroids. We also introduce some new classes of integral matroid polyhedra which extend a result of Edmonds. © 1988.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
