The multi-stripe travelling salesman problem

DOI10.1007/s10479-017-2513-4zbMath1380.90232arXiv1609.09796WikidataQ47145384 ScholiaQ47145384MaRDI QIDQ1698268

Eranda Çela, Gerhard J. Woeginger, Vladimir G. Deǐneko

Publication date: 15 February 2018

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.09796

zbMATH Keywords

computational complexity; combinatorial optimization; quadratic assignment problem; travelling salesman problem; kalmanson conditions; tractable special case

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90B80: Discrete location and assignment

Related Items

Pre-treatment of path problems with required lengths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The three-dimensional matching problem in kalmanson matrices
• Locating facilities which interact: Some solvable cases
• Extreme Hamiltonian lines
• The edge Hamiltonian path problem is NP-complete
• A canonical decomposition theory for metrics on a finite set
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• A solvable case of the quadratic assignment problem
• Proof of the Seymour conjecture for large graphs
• A partial k-arboretum of graphs with bounded treewidth
• New classes of efficiently solvable generalized traveling salesman problems
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• Hamiltonian powers in threshold and arborescent comparability graphs
• The Steiner tree problem in Kalmanson matrices and in circulant matrices
• The quadratic assignment problem. Theory and algorithms
• A note on circular decomposable metrics
• Perspectives of Monge properties in optimization
• When difference in machine loads leads to efficient scheduling in open shops
• Four-point conditions for the TSP: the complete complexity classification
• The symmetric quadratic traveling salesman problem
• On the Complexity of Master Problems
• Assignment Problems and the Location of Economic Activities
• Easy problems for tree-decomposable graphs
• Assignment Problems
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• Powers of Hamiltonian paths in interval graphs
• Sometimes Travelling is Easy: The Master Tour Problem
• The structure of circular decomposable metrics
• Edgeconvex Circuits and the Traveling Salesman Problem