ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST

The Traveling Salesman Problem and P vs. NP: Some 1960s Theoretical Work at NIST On the Complexity of Mathematical Algorithms.

Jack Edmonds
University of Waterloo

Friday, October 10, 2014 14:00-16:00,
Building 101, Portrait Room
Friday, October 10, 2014 12:00-14:00,
Room 1-4058


An informal description for a general audience of some basic mathematical theory developed at NBS, and a bit of reminiscing about important mathematical NBS colleagues, Alan Hoffman, Alan Goldman, and Christoph Witzgall.

The TSP is to find an optimum way for a stylus or a salesman to move through any prescribed set of points. It turns out to still be algorithmically difficult. The most famous of unsolved mathematical questions is still whether or not the TSP will forever remain intrinsically difficult.

While researching the TSP at NBS, some other seemingly difficult algorithmic problems were nicely solved.

Presentation Slides: PDF

Contact: B. Cloteaux

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2014-10-10.