A characterization of Linearizable instances of the Quadratic Traveling Salesman Problem
share
We consider the linearization problem associated with the quadratic traveling salesman problem (QTSP). Necessary and sufficient conditions are given for a cost matrix Q of QTSP to be linearizable. It is shown that these conditions can be verified in O(n^7) time. Some simpler sufficient conditions for linearization are also given along with related open problems.
READ FULL TEXT