DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
AD0679986
Title:
BLOCKING POLYHEDRA
Descriptive Note:
Corporate Author:
RAND CORP SANTA MONICA CA
Report Date:
1968-12-01
Pagination or Media Count:
34.0
Abstract:
A geometric theory of blocking polyhedra is developed and applied to a number of problems in extremal combinatorics. The basic notion is a variant of the concept of polar polyhedra and exhibits a similar duality. The max-flow min-cut equality and the length-width inequality, valid for paths and cuts in a network, always hold for a blocking pair of polyhedra, and the former of these characterizes the blocking relation. A typical combinatorial application is a new geometric characterization of the permutation matrices as the extreme points of a certain unbounded convex polyhedron.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE