Location and Distribution of Local Optima

Abstract

In this paper, we present a probabilistic analysis of the time versus solution quality tradeoff of different implementations of a basic sequential edge exchange procedure for a Traveling Salesman Problem. Our TSP will be on a complete graph with edge weights assigned independently and identically according to a Bernoulli distribution. One implementation of the procedure is a generalization of the Lin-Kernighan heuristic. For this implementation, we find asymptotic performance guarantees which decrease geometrically as the depth of the search increases. The basic search procedure may be implemented using a 2- change neighborhood structure. This enables us to find an asymptotic performance guarantee for a 2-opt procedure.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 30, 1992
Accession Number
ADA257791

Entities

People

  • Donna C. Llewellyn
  • Logan Whitaker

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Bernoulli Distribution
  • Computer Programming
  • Engineering
  • Game Theory
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • New York
  • Operations Research
  • Optimization
  • Polynomials
  • Probability
  • Random Variables
  • Systems Engineering

Fields of Study

  • Mathematics

Readers

  • Operations Research
  • Regression Analysis.