A clutter L is a collection of subsets of a ground set E(L) with the property that, for every pair A(i), A(j) is-an-element-of L, A(i) is neither contained in nor contains A(j). A cover of L is a subset of E intersecting every member of L. The covering polytope Q(L), associated with a clutter L, is the convex hull of the incidence vectors of the covers of L. The polytope Q(L) provides a common generalization for several polytopes associated with combinatorial optimization problems (stable set, knapsack, acyclic subdigraph, bipartite subgraph, etc.) that can be formulated as covering problems with respect to suitably defined clutters. In this paper, a binary composition operation is described, the clutter amalgam, that combines two clutters L1 and L2 to produce a new clutter L called amalgam of L1 and L2. Furthermore, an isomorphic polyhedral composition operation is introduced that combines the linear descriptions of the polytopes Q(L1) and Q(L2) and produces a linear description of the polytope Q(L). The clutter amalgam operation has the crucial property that if the clutters L1 and L2 are ideal then the amalgam L is also ideal. Finally, the restriction of the clutter amalgam to graphs properly generalizes the graph amalgam introduced by Burlet and Fonlupt and defines a new perfection-preserving operation.

Polyhedral Properties of Clutter Amalgam

NOBILI, Paolo;
1993

Abstract

A clutter L is a collection of subsets of a ground set E(L) with the property that, for every pair A(i), A(j) is-an-element-of L, A(i) is neither contained in nor contains A(j). A cover of L is a subset of E intersecting every member of L. The covering polytope Q(L), associated with a clutter L, is the convex hull of the incidence vectors of the covers of L. The polytope Q(L) provides a common generalization for several polytopes associated with combinatorial optimization problems (stable set, knapsack, acyclic subdigraph, bipartite subgraph, etc.) that can be formulated as covering problems with respect to suitably defined clutters. In this paper, a binary composition operation is described, the clutter amalgam, that combines two clutters L1 and L2 to produce a new clutter L called amalgam of L1 and L2. Furthermore, an isomorphic polyhedral composition operation is introduced that combines the linear descriptions of the polytopes Q(L1) and Q(L2) and produces a linear description of the polytope Q(L). The clutter amalgam operation has the crucial property that if the clutters L1 and L2 are ideal then the amalgam L is also ideal. Finally, the restriction of the clutter amalgam to graphs properly generalizes the graph amalgam introduced by Burlet and Fonlupt and defines a new perfection-preserving operation.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11587/107189
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 5
social impact