Probabilistic Algorithm for the Directed Traveling Salesman Problem

J. Michael Steele
J. Michael Steele
Department of Statistics, Princeton University, Princeton, New Jersey 08544
Search for more papers by this author

Department of Statistics, Princeton University, Princeton, New Jersey 08544

Published Online:1 May 1986https://doi.org/10.1287/moor.11.2.343

Abstract

A model is given for a random directed traveling salesman problem (DTSP). The asymptotic behavior of the optimal solution of the DTSP is determined, and this result is used to establish an ϵ-optimal probabilistic algorithm for solving the DTSP in polynomial time.

cover image Mathematics of Operations Research

Volume 11, Issue 2

May 1986

Pages 193-384

Article Information

Metrics

Information

Published Online:May 01, 1986

Cite as

J. Michael Steele, (1986) Probabilistic Algorithm for the Directed Traveling Salesman Problem. Mathematics of Operations Research 11(2):343-350.

https://doi.org/10.1287/moor.11.2.343

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Probabilistic Algorithm for the Directed Traveling Salesman Problem

Abstract

Volume 11, Issue 2

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News