  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 $\Theta(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 (2010), we show that when optimizing over the convex hull of the
permutation vectors (the permutahedron), we can reduce the number of variables
and constraints to $\Theta(n \log n)$ in theory and $\Theta(n \log^2 n)$ in
practice. We modify the recent convex formulation of the 2-SUM problem
introduced by Fogel et al. (2013) to use this polytope, and demonstrate how we
can attain results of similar quality in significantly less computational time
for large $n$. To our knowledge, this is the first usage of Goemans' compact
formulation of the permutahedron in a convex optimization problem. We also
introduce a simpler regularization scheme for this convex formulation of the
2-SUM problem that yields good empirical results.
