BLOCKING POLYHEDRA

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1968
Accession Number
AD0679986

Entities

People

  • D. R. Fulkerson

Organizations

  • RAND Corporation

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Graph Theory
  • Inequalities
  • Linear Programming
  • Linear Systems
  • Mathematics
  • Network Science
  • Permutations
  • United States

Readers

  • Operations Research
  • Parallel and Distributed Computing.