assignment polytope

GPTKB entity

Statements (22)
Predicate Object
gptkbp:instanceOf gptkb:Polygon
gptkbp:alsoKnownAs gptkb:Birkhoff_polytope
gptkbp:definedIn convex hull of n x n permutation matrices
gptkbp:dimensions (n-1)^2 for n x n matrices
gptkbp:facetDescription doubly stochastic matrices
gptkbp:form discrete mathematics
optimization
polyhedral combinatorics
https://www.w3.org/2000/01/rdf-schema#label assignment polytope
gptkbp:namedAfter gptkb:Garrett_Birkhoff
gptkbp:property all vertices are integral
each row and column sum to 1
faces correspond to partial assignments
gptkbp:relatedTo gptkb:Birkhoff–von_Neumann_theorem
combinatorial optimization
linear programming
gptkbp:studiedBy 1946
gptkbp:usedIn assignment problem
transportation problem
gptkbp:vertices permutation matrices
gptkbp:bfsParent gptkb:Birkhoff_polytope
gptkbp:bfsLayer 6