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
