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

In this paper, we investigate the maximum traveling salesman problem (Max-TSP) on quasi-banded matrices. A matrix is quasi-banded with multiplier α if all its elements contained within a band of several diagonals above and below the principal diagonal are non-zero, and any element in the band is at...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2002-06, Vol.119 (1), p.139-148
Main Authors: Blokh, David, Levner, Eugene
Format: Article
Language:English
Subjects:
Approximation algorithms with performance guarantees
Banded matrices
Maximum traveling salesman problem
Polynomial algorithm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we investigate the maximum traveling salesman problem (Max-TSP) on quasi-banded matrices. A matrix is quasi-banded with multiplier α if all its elements contained within a band of several diagonals above and below the principal diagonal are non-zero, and any element in the band is at least α times larger than the maximal element outside the band. We investigate the properties of the Max-TSP on the quasi-banded matrices, prove that it is strongly NP-hard and derive a linear-time approximation algorithm with a guaranteed performance.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(01)00270-0