Accession Number : ADA019547

Title :   A Subtour Elimination Algorithm for the Bottleneck Traveling Salesman Problem.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Smith,T. H. C. ; Thompson,G. L.

Report Date : OCT 1975

Pagination or Media Count : 37

Abstract : In this paper we propose a LIFO implicit enumeration algorithm for the bottleneck traveling salesman problem which uses the bottleneck assignment problem as a relaxation. We also present computational experience on a UNIVAC 1108 with symmetric and asymmetric problems, ranging in size from 30 to 2000 nodes. Our results indicate that for asymmetric problems the time requirement of the proposed algorithm grows slower than the square of the problem size -- i.e. the algorithm is empirically good (in the sense of Edmonds). (Author)

Descriptors :   *Algorithms, *Integer programming, *Operations research, Problem solving, Nodes, Hamiltonian, Transportation, Scheduling, Network flows, Digital computers, Computer programming

Subject Categories : Theoretical Mathematics
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE