Birkhoff Polytope

The Birkhoff polytope Bn, also called the assignment polytope, the polytope of doubly stochastic matrices, or the perfect matching polytope of the complete bipartite graph, is the convex polytope in RN (where N = n²) whose points are the doubly stochastic matrices, i.e., the n × n matrices whose entries are non-negative real numbers and whose rows and columns each add up to 1.

Read more about Birkhoff PolytopeGeneralizations

Other articles related to "polytopes, birkhoff polytope, polytope":

Polyhedral Combinatorics - Facets of 0-1 Polytopes
... methods for integer programming to be able to describe accurately the facets of polytopes that have vertices corresponding to the solutions of combinatorial optimization problems ... problems have solutions that can be described by binary vectors, and the corresponding polytopes have vertex coordinates that are all zero or one ... As an example, consider the Birkhoff polytope, the set of n × n matrices that can be formed from convex combinations of permutation matrices ...
Birkhoff Polytope - Generalizations
... The Birkhoff polytope is a special case of the transportation polytope, a polytope of nonnegative rectangular matrices with given row and column sums ... The integer points in these polytopes are called contingency tables they play an important role in Bayesian statistics ... The Birkhoff polytope is a special case of the matching polytope, defined as a convex hull of the perfect matchings in a finite graph ...