New semidefinite programming relaxations for the Linear Ordering and the Traveling Salesman Problem

In this paper we strengthen the relaxation proposed by Newman (2004) [43] and conduct a polyhedral study of the corresponding polytope. Furthermore we relate the relaxation to other linear and semidefinite relaxations for the (LOP) and for the Traveling Salesman Problem and elaborate on its connection to the Max Cut problem.