
Accession Number : AD0765750
Title : Investigations in the Theory of Blocking Pairs of Polyhedra.
Descriptive Note : Technical rept.,
Corporate Author : CORNELL UNIV ITHACA N Y DEPT OF OPERATIONS RESEARCH
Personal Author(s) : Weinberger,David B.
Report Date : AUG 1973
Pagination or Media Count : 95
Abstract : The basic theory of blocking pairs of polyhedra is described, and several combinatorial situations are explored in the report. First, a heretofore open question concerning tours in a complete graph is resolved. Then a study is made of blocking pairs that arise in a network flow context. In particular, the blocking polyhedron of the polyhedron generated by all integral feasible flows is determined for uncapacitated supplydemand networks, capacitated supplydemand networks, and circulation networks (with integral data). A simple algorithm is given for solving the associated integral packing problems. These results are then used to demonstrate the validity for partition matroids of a conjecture concerning the intersection of two arbitrary matroids. Also, these results are applied to roundrobin tournaments, (0,1)matrices with prescribed row and column sums, and flow arborescences. (Author)
Descriptors : (*COMBINATORIAL ANALYSIS, OPTIMIZATION), (*MATHEMATICAL PROGRAMMING, ALGORITHMS), MATRICES(MATHEMATICS), INEQUALITIES, SIMPLEX METHOD, GRAPHICS, SET THEORY, THEOREMS, THESES
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE