Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0675.90054
Cornuéjols, Gérard; Sassano, Antonio
On the 0,1 facets of the set covering polytope. (English)
[J] Math. Program., Ser. A 43, No.1, 45-55 (1989). ISSN 0025-5610; ISSN 1436-4646/e

Necessary and sufficient conditions for an inequality with 0-1 coefficients to define a facet of the set covering polytope associated with the 0-1 constraint matrix A are given. The work is influenced by the results on the set packing problem, where also the notations are defined in the intersection graph of A. For the case that A is a matrix of odd order and the matrix $H<A$ contains exactly two ones per row and per column it is shown how to decide in polynomial time whether $\sum\sp{n}\sb{j=1}x\sb j>(n+1)/2$ is valid. This yields a facet of the set covering polytope.
[N.Yanev]

MSC 2000:: *90C09 Boolean programming
52Bxx Polytopes and polyhedra
05C70 Factorization, etc.
90C35 Network programming
90C10 Integer programming

Keywords: facet; set covering polytope; set packing; intersection graph

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]