Statistical Analysis of Some Traveling Salesman Algorithms.

Abstract

This paper reports the results of a statistical analysis of the performance of three branch and bound algorithms for the general (asymmetric) traveling salesman problem on randomly generated test problems with up to 325 cities. Three types of functions, polynomial, superpolynomial (long-exponential) and exponential, were fitted to the performance data of each of the algorithms by least squares techniques. The three functions describe almost equally well the behavior of the algorithms in the range of problem sizes examined.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1984
Accession Number
ADA145786

Entities

People

  • E. Balas
  • Paolo Toth
  • T. W. Mcguire

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Coefficients
  • Data Science
  • Exponential Functions
  • Inequalities
  • Information Science
  • Linear Programming
  • Numbers
  • Polynomials
  • Probability Distributions
  • Schools
  • Simplex Method
  • Statistical Analysis
  • Statistics
  • Trees (Data Structures)
  • Universities

Readers

  • Atmospheric Science / Meteorology, specifically Wind Wave Turbulence.
  • Graph Algorithms and Convex Optimization.
  • Statistical inference.