An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices
type: Item
instance of: scholarly article
title: An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices
zbMATH Open document ID: 1041.90073
DOI: 10.1016/S0166-218X(01)00270-0
author: David Blokh
author: Eugene Levner
published in: Discrete Applied Mathematics
publication date: 2002-06-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 1758392
zbMATH Keywords: banded matrices
reviewed by: Horst W. Hamacher
MaRDI profile type: Publication
cites work: Two Algorithmic Results for the Traveling Salesman Problem
cites work: Q3840359
cites work: Assignment problem for three-index Jacobi matrices
cites work: Maximizing traveling salesman problem for special matrices
cites work: THE MAXIMUM TRAVELING SALESMAN PROBLEM ON BANDED MATRICES
cites work: Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
cites work: An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
cites work: Q4198056
cites work: An approximation algorithm for the maximum traveling salesman problem
cites work: Gilmore-Gomory type traveling salesman problems
cites work: Q4882993
cites work: Q5187226
description: scientific article; zbMATH DE number 1758392