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).
Abstract
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 |
| Date accepted: | No date available |
| Date deposited: | No date available |
| Date of first online publication: | 2010 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
