  Recently, Sinkhorn's algorithm was applied for approximately solving linear
programs emerging from optimal transport very efficiently. This was
accomplished by formulating a regularized version of the linear program as
Bregman projection problem onto the polytope of doubly-stochastic matrices, and
then computing the projection using the efficient Sinkhorn algorithm, which is
based on alternating closed-form Bregman projections on the larger polytopes of
row-stochastic and column-stochastic matrices. In this paper we suggest a
generalization of this algorithm for solving a well-known lifted linear program
relaxations of the Quadratic Assignment Problem (QAP), which is known as the
Johnson Adams (JA) Relaxation. First, an efficient algorithm for Bregman
projection onto the JA polytope by alternating closed-form Bregman projections
onto one-sided local polytopes is devised. The one-sided polytopes can be seen
as a high-dimensional, generalized version of the row/column-stochastic
polytopes. Second, a new method for solving the original linear programs using
the Bregman projections onto the JA polytope is developed and shown to be more
accurate and numerically stable than the standard approach of driving the
regularizer to zero. The resulting algorithm is considerably more scalable than
standard linear solvers and is able to solve significantly larger linear
programs.
