Abstract (Gregory Gutin)

Local search (LS) is a widely used, general approach to solving hard optimization problems. Over the last few years there has been renewed activity on LS: both on the experimental front with the design of faster algorithms that find reasonable solutions in reasonable amount of time for very large instances of combinatorial optimization problems such as the Traveling Salesman Problem, and on the theoretical front with the development of a complexity theory of LS as well as some ``new'' approaches in LS such as LS in exponential size neighbourhoods (in polynomial time). The talk is mostly devoted to the second front (results and open problems).
Last modified: December 20, 1996.
Kim Skak Larsen (kslarsen@imada.sdu.dk)