A characterization of Linearizable instances of the Quadratic Traveling Salesman Problem

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.

Cited by in corpus (3)

• Geometric and LP-based heuristics for the quadratic travelling salesman problem
• Representations of quadratic combinatorial optimization problems: A case study using the quadratic set covering problem
• The linearization problem of a binary quadratic problem and its applications