publication . Article . 1972

Anti-blocking polyhedra

D.R Fulkerson;
Open Access English
  • Published: 01 Feb 1972 Journal: Journal of Combinatorial Theory, Series B, issue 1, pages 50-71 (issn: 00958956, Copyright policy)
  • Publisher: Published by Elsevier Inc.
Abstract
A theory parallel to that for blocking pairs of polyhedra is developed for anti-blocking pairs of polyhedra, and certain combinatorial results and problems are discussed in this framework. Blocking pairs of polyhedra are intimately related to maximum packing problems, anti-blocking pairs to minimum covering problems. Let B = {x ∈ R+n | Ax ≤ 1}, where A is a non-negative matrix and 1 = (1,…, 1). The anti-blocker of the convex polyhedron B is defined to be the convex polyhedron B = {x ∈ R+n | x · B ≤ 1}. It is shown that B = B and a method is described for finding a non-negative matrix B such that B={x ∈ R+itn | Bx ≤ 1}. In particular, if A is the incidence matrix...
Subjects
free text keywords: Theoretical Computer Science, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Integer, Discrete mathematics, Polyhedron, Perfect graph, Incidence matrix, Convex polytope, Convex hull, Combinatorics, Family of sets, Extremal combinatorics, Mathematics
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue