A class of exponential neighbourhoods for the quadratic travelling salesman problem

Brad D. Woods () and Abraham P. Punnen ()
Additional contact information
Brad D. Woods: Simon Fraser University
Abraham P. Punnen: Simon Fraser University

Journal of Combinatorial Optimization, 2020, vol. 40, issue 2, No 2, 303-332

Abstract: Abstract The quadratic travelling salesman problem (QTSP) is to find a least-cost Hamiltonian cycle in an edge-weighted graph, where costs are defined on all pairs of edges such that each edge in the pair is contained in the Hamiltonian cycle. This is a more general version than the one that appears in the literature as the QTSP, denoted here as the adjacent quadratic TSP, which only considers costs for pairs of adjacent edges. Major directions of research work on the linear TSP include exact algorithms, heuristics, approximation algorithms, polynomially solvable special cases and exponential neighbourhoods (Gutin G, Punnen A (eds): The traveling salesman problem and its variations, vol 12. Combinatorial optimization. Springer, New York, 2002) among others. In this paper we explore the complexity of searching exponential neighbourhoods for QTSP, the fixed-rank QTSP, and the adjacent quadratic TSP. The fixed-rank QTSP is introduced as a restricted version of the QTSP where the cost matrix has fixed rank p. It is shown that fixed-rank QTSP is solvable in pseudopolynomial time and admits an FPTAS for each of the special cases studied, except for the case of matching edge ejection tours. The adjacent quadratic TSP is shown to be polynomially-solvable in many of the cases for which the linear TSP is polynomially-solvable. Interestingly, optimizing over the matching edge ejection tour neighbourhood is shown to be pseudopolynomial for the rank 1 case without a linear term in the objective function, but NP-hard for the adjacent quadratic TSP case. We also show that the quadratic shortest path problem on an acyclic digraph can be solved in pseudopolynomial time and by an FPTAS when the rank of the associated cost matrix is fixed.

Keywords: Quadratic travelling salesman problem; Travelling salesman problem; Combinatorial optimization; Quadratic 0–1 programming (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00588-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:40:y:2020:i:2:d:10.1007_s10878-020-00588-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00588-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().