Discrete Mathematics and Optimization Seminar
Mar. 1st, 2010
On the hardness of losing weight
Andrei Krokhin
Local search algorithms iteratively improve solutions by checking whether it is possible to find a better solution in the local neighborhood of the current solution. The local neighborhood is usually defined as the set of solutions that can be obtained by one (or more generally, at most k for some fixed k) elementary changes. Large values of k can give better results; however, the brute force search of the local neighborhood is not feasible for larger k. Parameterized complexity gives a convenient framework for studying the question whether there is an efficient way of searching the local neighborhood. In the talk, I will briefly overview parameterized complexity, summarize recent results in this direction, and explain in more detail the analysis of the problem of finding minimum weight solutions for Boolean CSP.

(Joint work with Dániel Marx)