A characterization of Linearizable instances of the Quadratic Traveling Salesman Problem

2017/08/23 by Abraham P. Punnen, Punnen, Abraham P., Walter, Matthias +2
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.1708.07217

openalex publication_date 2017/08/23 · openalex created_date 2017/08/31 · openalex updated_date 2026/07/28

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⁵) time. Some simpler sufficient conditions for linearization are also given along with related open problems.

Related

• Linearizable special cases of the QAP
• The linearization problem of a binary quadratic problem and its applications
• The traveling salesman problem: A Linear programming formulation
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems
• The multi-stripe travelling salesman problem