Next: Bert Hartnell - The Up: Discrete Mathematics / Mathématiques Previous: Shannon Fitzpatrick - The
Gregory Gutin - Polynomially searchable sets of tours for the travelling salesman problem: theoretical and experimental results
GREGORY GUTIN, Department of Mathematics and Statistics, Brunel, The University of West London, Uxbridge UB8 3PH, UK | |
Polynomially searchable sets of tours for the travelling salesman problem: theoretical and experimental results |
For an -hard combinatorial optimization problem P, a set S of solutions is called polynomially searchable if the best solution in S can be found in polynomial time (in size of P). We describe some sets of tours for the asymmetric that can be used in construction and local search type algorithms. We present theoretical and computational results on these sets.
eo@camel.math.ca