Abstract
We consider independence system polytopes, i.e. polytopes whose extreme points are the incidence vectors of the sets of an independence system. We first give a sufficient condition for recognizing Boolean facets. Then, the notion of antiweb introduced by Trotter for graphs is generalized to independence systems and used for obtaining canonical facets of the associated polytopes. We also point out how our results relate with known ones for knapsack, set covering and matroid polytopes.
Similar content being viewed by others
References
C. Berge,Graphs and Hypergraphs (Dunod, Paris, 1970).
E. Balas, “Facets of the knapsack polytope,”Mathematical Programming 8 (1975) 146–164.
E. Balas and E. Zemel, “Critical cutsets of graphs and canonical facets of set packing polytopes,”Mathematics of Operations Research (1977) 15–19.
E. Balas and E. Zemel, “Facets of the knapsack polytope from minimal covers,”SIAM Journal of Applied Mathematics 34 (1978) 119–148.
V. Chvátal, “On certain polytopes associated with graphs,”Journal of Combinatorial Theory (B) 18 (1975) 138–154.
M. Conforti and M. Laurent, “On the facial structure of independence system polyhedra,”Mathematics of Operations Research, to appear.
G. Cornuéjols and A. Sassano, “On the 0, 1 facets of the set covering polytope,”Mathematical Programming 43 (1989) 45–55.
J. Edmonds, “Matroids and the greedy algorithm,”Mathematical Programming 1 (1971) 127–136.
J. Edmonds, “Matroid intersection,”Annals of Discrete Mathematics 4 (1979) 39–49.
R. Euler, M. Junger and G. Reinelt, “Generalizations of cliques, odd cycles and anticycles and their relation to independence system polyhedra,” preprint, University of Augsburg.
R. Giles, “Submodular functions, graphs and integer polyhedra,” Ph.D. thesis, University of Waterloo (1975).
G.L. Nemhauser and L.E. Trotter, “Properties of vertex packing and independence system polyhedra,”Mathematical Programming 6 (1974) 48–61.
M.W. Padberg, “On the facial structure of set packing polyhedra,”Mathematical Programming 5 (1973) 199–215.
M.W. Padberg, “A note on zero–one programming,”Operations Research 23 (1975) 833–837.
A. Sassano, “On the facial structure of the set covering polytope,”Mathematical Programming, to appear.
Y. Sekiguchi, “A note on node packing problems on hypergraphs,”Operations Research Letters 2(5) (1983) 243–247.
L.E. Trotter, “A class of facet producing graphs for vertex packing polyhedra,”Discrete Mathematics 12 (1975) 373–388.
D. Welsh,Matroid Theory (Academic Press, New York, 1976).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Laurent, M. A generalization of antiwebs to independence systems and their canonical facets. Mathematical Programming 45, 97–108 (1989). https://doi.org/10.1007/BF01589098
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01589098