A useful transform of standard input data for a classical NP-complete problem
type: Item
instance of: scholarly article
title: A useful transform of standard input data for a classical NP-complete problem
zbMATH Open document ID: 0564.90085
DOI: 10.1016/0377-2217(85)90135-3
author: Francesco A. Brunacci
published in: European Journal of Operational Research
publication date: 1985-01-01T00:00:00Z
review text: The archetypal symmetric travelling salesman problem can be seen in a new and interesting way, by using first a standard preparatory phase of input data, and then by applying a transform from the set D of 'distances' among 'cities' and the set B of 'loss of optimality'. The specific form of the \(D\to B\) transform is introduced and discussed. In order to show in realistic terms the interest of the approach proposed, a class of 'diffusive' heuristic procedures operating from B is defined. An example of solution by an algorithm included in this class is completely worked out; an outline of computational tests done on the same algorithm is also given.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3900542
zbMATH Keywords: equivalent transformation
zbMATH Keywords: symmetric travelling salesman
zbMATH Keywords: 'diffusive' heuristic procedures
zbMATH Keywords: computational tests
MaRDI profile type: Publication
full work available at URL: 0377-2217(85)90135-3
OpenAlex ID: W2030982882
cites work: Q4198056
cites work: Q4184789
cites work: Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
cites work: Approximate Traveling Salesman Algorithms
cites work: A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
cites work: Local Search for the Asymmetric Traveling Salesman Problem
cites work: A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
cites work: Probabilistic analysis of solving the assignment problem for the traveling salesman problem
cites work: Q3039069
cites work: The NP-completeness column: An ongoing guide
Recommended article: Survey of polynomial transformations between NP-complete problems
Recommended article: Q4889464
Recommended article: Q3221973
Recommended article: Q3340499
Recommended article: Q4298845
Recommended article: Algorithmic Applications in Management
Recommended article: Solving the \(k\)-cardinality assignment problem by transformation
Recommended article: On the classification of NP-complete problems in terms of their correlation coefficient
Recommended article: Linear Transformations in Boolean Complexity Theory
Recommended article: On completeness for NP via projection translations
description: scientific article; zbMATH DE number 3900542