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):

Report Date:

1973-08-01

Pagination or Media Count:

95.0

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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE