Investigations in the Theory of Blocking Pairs of Polyhedra.
CORNELL UNIV ITHACA N Y DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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
- Operations Research