## Beyond the Birkhoff Polytope: Convex Relaxations for Vector Permutation Problems

The Birkhoff polytope (the convex hull of the set of permutation matrices) is frequently invoked in formulating relaxations of optimization problems over permutations. The Birkhoff polytope is represented using Θ(n^2) variables and constraints, significantly more than the n variables one could use to represent a permutation as a vector. Using a recent construction of Goemans … Read more