Recent development in parameterized complexity theory has revealed abundant sophisticatd local solution structures for many intractable combinational optimization problems. Techniques and results developed in the area have given rise to the consideration that these solution structures can be closely related to neighborhoods in local search heuristics. This project is to investigate such a relationship and, based on which, to develop innovative techniques for the design of effective local search: computational complexity and performance guarantee.
Parameterization on neighborhoods is introduced to scrutinize the relationship between neighborhoods and the computational complexity of local search algorithms. This approach will essentially show what quantities in a sophisticated neighborhood make the algorithms converge fast. It is also expected to demonstrate how difficult in terms of complexity to improve the effectiveness of a simple neighborhood. A systematic technique is also investigated to derive neighborhoods from existing techniques used in parameterized tractibility. This will result in a general framework for the design of effective local search algorithms for various parameterized tractable optimization problems.
