This file records (some of) the best known lengths of Hamiltonian tours for two sets of input data, as discovered by programs written by Ryan Hayward's fall 2001 CS670 (Combinatorial Optimization) students, as well as the CONCORDE/LINKERN value found. The input data was generated by Bill Cook. The CONCORDE program was written by Applegate/Bixby/Chvatal/Cook. ******************************************************************************* 4663 Canadian geographic locations Oct 1 Jim Nastos 47 893 359.167969 Oct 2 Fred Vizeacoumar 12 004 552.135034 (sorted y co-ordinates) Oct 12 Fred Vizeacoumar 1 649 944.638216 (nearest neighbour) Oct 5 Daniel Neilson 1 640 359.25 (inductive method) Oct 3 Shubhashis Ghosh 1 612 185.637798 (nearest neighbour, start 4606) Oct 9 Chi Hoon Lee 1 612 12*.****** Oct 3 Ashikur Rahman 1 558 873.125 (modified NN, start 2649) Oct 2 Jim Nastos 1 512 356.47559 (quasi-NN, start 4049) Oct 6 Daniel Neilson 1 489 238.891602 (closest vertex to cycle-so-far) Oct 9 Changyu Yin 1 404 312.25 (modified 2-opt NN, start 1237) Oct 10 Shubhashis Ghosh 1 390 465.901203 (modified 2-opt NN, start 251) Oct 10 Changyu Yin 1 361 549.125 (modified 2-opt NN, start 100) Oct 31 Yin/Nastos 1 344 047.375 (2-opt, linkern, random start) 1 320 957 (CONCORDE:LINKERN, 0.49 seconds) Nov 19 Yin/Nastos 1 318 164.750 () Nov 19 1 290 664. (CONCORDE:LINKERN, overnight) ******************************************************************************* 588 New Jersey locations Oct 18 Fred Vizeacoumar 32 912.6 (nearest neighbour, start 519) Oct 17 Jim Nastos 32 521.3 (iterative quasi NN, start 469) Oct 30 Shubhashis Ghosh 28 185.616 (modified 2-opt NN, start 260) 27 008 (CONCORDE:LINKERN, 0.04 seconds) Nov 16 Yin/Nastos 26 942.689453 (4-interchanges) 26 767 (CONCORDE:LINKERN, 1178.43 s) *******************************************************************************