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
Distribution Statement : APPROVED FOR PUBLIC RELEASE