Investigations in the Theory of Blocking Pairs of Polyhedra.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1973
- Accession Number
- AD0765750
Entities
People
- David B. Weinberger
Organizations
- Cornell University