On the facial structure of independence system polyhedra

On the facial structure of independence system polyhedra

0.00 Avg rating0 Votes
Article ID: iaor1988178
Country: United States
Volume: 13
Issue: 4
Start Page Number: 543
End Page Number: 555
Publication Date: Nov 1988
Journal: Mathematics of Operations Research
Authors: ,
Keywords: mathematics
Abstract:

A polyhedron P whose extreme points are the incidence vectors of the sets of an independence system ℐ is called an independence system polyhedron. In this paper, the authors consider the problem of describing the facial structure of independence system polyhedra. Using the fact that this structure is known when the independence system is a matroid, they study the polyhedron P by decomposing the independence system ℐ as a union of matroidal families. The authors provide a system of valid inequalities for P that contains all its facets. A consequence of this result is the following: the maximum number of distinct coefficients of a facet is bounded by the minimum number of matroidal families whose union gives ℐ. When the independence system ℐ is the union of two matroids, the authors give necessary and sufficient conditions for an inequality of the above system to define a facet of P.

Reviews

Required fields are marked *. Your email address will not be published.