ISSN:
1436-4646
Keywords:
Independence systems
;
set covering
;
polytope
;
facet
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Given a family of subsetsℱ of an arbitrary groundsetE, acover ofℱ is any setC ⊂E having non-empty intersection with every subset inℱ. In this paper we deal with thecovering polytope, i.e., the convex hull of the incidence vectors of all the covers ofℱ. In Section 2 we review all the known properties of the covering polytope. In Sections 3 and 4 we introduce two new classes of non-Boolean facets of such a polytope. In Sections 5 and 6 we describe some non-sequential lifting procedures. In Section 7 a generalization of the notion ofweb introduced by L.E. Trotter is presented together with the facets of the covering polytope produced by such a structure. Moreover, the strong connections between several combinatorial problems and the covering problem are pointed out and, exploiting those connections, some examples are presented of new facets for the Knapsack and Acyclic Subdigraph polytopes.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01589100
