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

From MaRDI portal
Revision as of 04:03, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices
scientific article

    Statements

    An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices (English)
    0 references
    0 references
    0 references
    24 June 2002
    0 references
    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.
    0 references
    banded matrices
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references