For those who might not subscribe to the Math Forum Newsletter,
http://forum.swarthmore.edu/electronic.newsletter/mfin.faq.html , the
following was in this week's issue and might be of interest to you:
THE TRAVELING SALESMAN
The problem: find the length of the shortest closed tour visiting N
cities. Here are a few sites to
explore:
TSPBIB (TRAVELING SALESMAN PROBLEM) - Pablo
Moscato
http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html
A comprehensive listing of papers, source code, preprints, and
technical reports available on the
Internet about the Traveling Salesman Problem (TSP) and some
associated problems such as Fractal TSP Instances and VRP
Instances, with links to software and Java applets that can be used
to explore the problem.
THE TRAVELING SALESMAN PROBLEM (TSP) - Vasek
Chvatal
http://www.cs.rutgers.edu/~chvatal/tsp.html
A collection of sites that includes a link to TSPLIB, Gerhard Reinelt's
library of some hundred instances of the problem, and to computer code
that has solved more
than twenty previously unsolved instances.
********THE TRAVELING SALESMAN PROBLEM - A REVIEW OFTHEORY AND
CURRENT RESEARCH - Mark H. Noschang
http://www.ececs.uc.edu/~mnoschan/sale.html
This paper introduces the concept in depth using informal examples and
formal graph theory notation,with discussions of common formulations,
some practical
applications, past and current heuristic approaches, and various
approximation algorithms. A bibliography of references is
included.
TRAVELING SALESMAN CONSTANTS - Steven Finch,
MathSoft
http://www.mathsoft.com/asolve/constant/sales/sales.html
Consider n distinct points in the d-dimensional unit cube. Of all
(n-1)!/2 closed paths (or tours)
passing through each point precisely once, what is the length
L(n,d) of the shortest such path? From Favorite
Mathematical Constants:
http://www.mathsoft.com/asolve/constant/constant.html
THE SHOELACE PROBLEM - Ivars Peterson
(MathTrek)
http://www.maa.org/mathland/mathtrek_2_8_99.html
How should shoes be laced? There are at least three common ways to lace
shoes, and the lacing style a person uses depends on a variety of
factors, ranging from
aesthetic appeal to tying efficiency. The shoelace question represents a
special, restricted instance of the classic traveling salesman
problem...
THE TRAVELING MONKEY - Ivars Peterson
(MathLand)
http://www.maa.org/mathland/mathland_7_7.html
It turns out that vervet monkeys can also solve the traveling
salesman problem; rather than
always heading for the nearest food supply, the monkeys apparently plan
their next three visits to minimize distance and travel time...
As ever,
Ethel
-- "To teach is to learn twice. "¨ Joseph Joubert (1754-1824).
Visit me at http://dimacs.rutgers.edu/~breuche