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 supply-demand networks, capacitated supply-demand 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 round-robin 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