DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE ODENSE UNIVERSITY Local Search for Combinatorial Optimization Gregory Gutin Brunel University Tuesday, January 7, 1997, at 2:15 PM The Seminar Room 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). Joergen Bang-Jensen