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