A characterization of Linearizable instances of the Quadratic Traveling Salesman Problem
classification
💻 cs.DM
cs.CC
keywords
conditionsproblemgivenlinearizablelinearizationqtspquadraticsalesman
read the original abstract
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^5)$ time. Some simpler sufficient conditions for linearization are also given along with related open problems.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.