
Discrete Mathematics and Optimization Seminar

Mar. 1st, 2010
On the hardness of losing weight
Andrei Krokhin
Durham

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)



