Premium
The greedy travelling salesman's problem
Author(s) -
Jenkyns T. A.
Publication year - 1979
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230090406
Subject(s) - travelling salesman problem , digraph , greedy algorithm , combinatorics , bottleneck traveling salesman problem , minimum weight , mathematics , 2 opt , enhanced data rates for gsm evolution , path (computing) , christofides algorithm , hamiltonian path , graph , mathematical optimization , discrete mathematics , computer science , artificial intelligence , programming language
The Travelling Salesman's Problem is to find a Hamilton path (or circuit) which has minimum total weight W * , in a graph (or digraph) with a non‐negative weight on each edge. The Greedy Travelling Salesman's Problem is “How much larger than W * can the total weight G * of the solution obtained by the Greedy Algorithm be?”. Using the theory of independence systems, it is shown that G * ‐W * may be as large as f(n,M,W * ) where n is the number of vertices and M is the maximum edge‐weight. The function f is determined for the several variations of the Travelling Salesman's Problem and the bound is shown to be best possible in each case.