An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices (Q1602709)

Given a complete graph \(G=(V,E)\) and weights \(w(i,j)\) for all edges \((i,j)\) in \(E\), the maximum travelling salesman problem looks for a tour through all nodes of the graph such that the sum of its weights is maximized. The problem is well-known to be NP-hard in the strong sense. The authors consider the special case, where the weight matrix \(W= w(i,j)\) is \((p,q)\)-quasi-banded with multiplier \(\alpha\), i.e. (1) all its elements contained within a band of \(p\) diagonals above the principal diagonal and \(q\) diagonals below it are non-zero, and (2) any element in the band is at least a times larger than the maximal element outside the band. While some results are known for the simplest symmetric case (i.e. \(p=q=1)\), the authors deal with the simplest asymmetrical case \(p=2\) and \(q=O\). They prove that this special case is NP-hard in the strong sense and propose a linear-time approximation algorithm with a guaranteed performance.