In this paper we describe a binary composition operation, the anti-join, which combines a pair of clutters L1 and L2 to give a new clutter L. The anti-join operation is, in some sense, the ''dual'' of the join operation, introduced by Cunningham [10]. In fact, it has the property that the blocker of the clutter L obtained by joining two clutters L1 and L2, is the anti-join of the blockers of L1 and L2. For such an operation we show how the linear descriptions of the polyhedra Q(L1) and Q(L2) have to be combined to produce a linear description of the polyhedron Q(L). Moreover, given a set F subset-or-equal-to {lambda: 0 less-than-or-equal-to lambda less-than-or-equal-to 1} such that {0, 1} subset-or-equal-to F and a is-an-element-o F if and only if (1-a) is-an-element-of F, we define the F-property for covering polyhedra as a proper generalization of the Fulkerson property, to which it reduces for F = {0, 1}. We prove that the anti-join operation preserves the F-property. This implies the characterization of the coefficients of the facet-defining inequalities for the cycle and cocycle polyhedra associated with graphs noncontractible to the four-wheel W4.

The Anti-join Composition and Polyhedra

NOBILI, Paolo;
1993

Abstract

In this paper we describe a binary composition operation, the anti-join, which combines a pair of clutters L1 and L2 to give a new clutter L. The anti-join operation is, in some sense, the ''dual'' of the join operation, introduced by Cunningham [10]. In fact, it has the property that the blocker of the clutter L obtained by joining two clutters L1 and L2, is the anti-join of the blockers of L1 and L2. For such an operation we show how the linear descriptions of the polyhedra Q(L1) and Q(L2) have to be combined to produce a linear description of the polyhedron Q(L). Moreover, given a set F subset-or-equal-to {lambda: 0 less-than-or-equal-to lambda less-than-or-equal-to 1} such that {0, 1} subset-or-equal-to F and a is-an-element-o F if and only if (1-a) is-an-element-of F, we define the F-property for covering polyhedra as a proper generalization of the Fulkerson property, to which it reduces for F = {0, 1}. We prove that the anti-join operation preserves the F-property. This implies the characterization of the coefficients of the facet-defining inequalities for the cycle and cocycle polyhedra associated with graphs noncontractible to the four-wheel W4.
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/107195
 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??? 2
social impact