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)