Large Exponential Neighbourhoods for the Traveling Salesman Problem
Anders Yeo · 1997
An exponential neighbourhood for the traveling salesman problem (TSP) is a set of tours, which grows exponentially in the input size. An exponential neighbourhood is polynomial time searchable if we can find the best among the exponential number of tours in polynomial time. Deineko and Woeginger asked if there exists polynomial time searchable neighbourhoods of size at least bffnc!, for some ff ? 1 2 , where n is the number of vertices in the TSP. In this paper we prove that such neighbourhoods exist for all ff ! 1. In fact we give a neighbourhood of size at least c n! k n , for any k ? 2 + ln k 1 (i.e. k ? 3:14619:::) and for some constant c (depending on k), which can be searched in O(n 3 ) time. Using a slight variation of the above algorithm we can search neighbourhoods of size bffnc! in time O(n 1+2ff ), for any 0 ! ff ! 1. Deineko and Woeginger proved (indirectly) that if P 6= NP then no algorithm for searching a neighbourhood of size bffnc! can run faster then O(n 1+ff ...