Krokhin, A. and Marx, D. (2010) 'On the hardness of losing weight.', in ICALP '08 Proceedings of the 35th international colloquium on Automata, Languages and Programming. Berlin, Heidelberg : Springer-Verlag , pp. 662-673. Lecture notes in computer science. (5125).
We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, and a solution to it, the question is whether there is a better (lighter, i.e., having strictly less Hamming weight) solution within a given distance from the initial solution. We classify the complexity, both classical and parameterized, of such problems by a Schaefer-style dichotomy result, that is, with a restricted set of allowed types of constraints. Our results show that there is a considerable amount of such problems that are NP-hard, but fixed-parameter tractable when parameterized by the distance.
|Item Type:||Book chapter|
|Keywords:||Constraint satisfaction problem, Local search, Complexity, Fixed-parameter tractability.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-540-70575-8_54|
|Record Created:||18 Dec 2009 11:05|
|Last Modified:||01 Jul 2011 14:27|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|