Facets and lifting procedures for the set covering polytope |
| |
Authors: | Paolo Nobili Antonio Sassano |
| |
Institution: | (1) Istituto di Analisi dei Sistemi ed Informatica del CNR, Viale Manzoni 30, 00185 Roma, Italy |
| |
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. |
| |
Keywords: | Independence systems set covering polytope facet |
本文献已被 SpringerLink 等数据库收录! |
|