{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:43Z","timestamp":1750307203022,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["PARAMTIGHT (280152)"],"award-info":[{"award-number":["PARAMTIGHT (280152)"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/C543831\/1 and EP\/C54384X\/1"],"award-info":[{"award-number":["EP\/C543831\/1 and EP\/C54384X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2151171.2151182","type":"journal-article","created":{"date-parts":[[2012,4,24]],"date-time":"2012-04-24T18:41:10Z","timestamp":1335292870000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["On the hardness of losing weight"],"prefix":"10.1145","volume":"8","author":[{"given":"Andrei","family":"Krokhin","sequence":"first","affiliation":[{"name":"Durham University, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"Budapest University of Technology and Economics, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,4,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"(eds.)","author":"Aarts E.","year":"2003","unstructured":"Aarts , E. and Lenstra , J . (eds.) 2003 . Local Search in Combinatorial Optimization. Princeton University Press , Princeton, NJ. Aarts, E. and Lenstra, J. (eds.) 2003. Local Search in Combinatorial Optimization. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-004-9419-y"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Cohen D. and Jeavons P. 2006. The complexity of constraint languages. In Handbook of Constraint Programming F. Rossi et al. Eds. Elsevier Ch. 8.  Cohen D. and Jeavons P. 2006. The complexity of constraint languages. In Handbook of Constraint Programming F. Rossi et al. Eds. Elsevier Ch. 8.","DOI":"10.1016\/S1574-6526(06)80012-X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Creignou N. Khanna S. and Sudan M. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems Vol. 7. SIAM Philadelphia PA.   Creignou N. Khanna S. and Sudan M. 2001. Complexity Classifications of Boolean Constraint Satisfaction Problems Vol. 7. SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898718546"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00146-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00174-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Downey R. and Fellows M. 1999. Parameterized Complexity. Springer Berlin.   Downey R. and Fellows M. 1999. Parameterized Complexity. Springer Berlin.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_8_1","volume-title":"Aspects of Complexity (Kaikura","author":"Fellows M.","year":"2000","unstructured":"Fellows , M. 2001. Parameterized complexity: New developments and research frontiers . In Aspects of Complexity (Kaikura , 2000 ), vol. 4 , de Gruyter , 51--72. Fellows, M. 2001. Parameterized complexity: New developments and research frontiers. In Aspects of Complexity (Kaikura, 2000), vol. 4, de Gruyter, 51--72."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.003"},{"key":"e_1_2_1_10_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer Berlin.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer Berlin."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Gu J. Purdom P. Franko J. and Wah B. 2000. Algorithms for the Satisfiability Problem. Cambridge University Press Cambridge UK.  Gu J. Purdom P. Franko J. and Wah B. 2000. Algorithms for the Satisfiability Problem. Cambridge University Press Cambridge UK.","DOI":"10.1007\/978-1-4757-3023-4_7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006318521185"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Hoos H. and Tsang E. 2006. Local search methods. In Handbook of Constraint Programming F. Rossi et al. Eds. Elsevier Ch. 5.  Hoos H. and Tsang E. 2006. Local search methods. In Handbook of Constraint Programming F. Rossi et al. Eds. Elsevier Ch. 5.","DOI":"10.1016\/S1574-6526(06)80009-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00037-3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0195-9"},{"key":"e_1_2_1_18_1","first-page":"7","article-title":"Local search","volume":"3","author":"Marx D.","year":"2008","unstructured":"Marx , D. 2008 a. Local search . Parameterized Complex. News 3 , 7 -- 8 . Marx, D. 2008a. Local search. Parameterized Complex. News 3, 7--8.","journal-title":"Parameterized Complex. News"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.02.008"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9326-z"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.07.004"},{"key":"e_1_2_1_22_1","unstructured":"Michiels W. Aarts E. and Korst J. 2007. Theoretical Aspects of Local Search. Springer Berlin.   Michiels W. Aarts E. and Korst J. 2007. Theoretical Aspects of Local Search. Springer Berlin."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0047-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02777-2_27"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2151171.2151182","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2151171.2151182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:19Z","timestamp":1750241179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2151171.2151182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2151171.2151182"],"URL":"https:\/\/doi.org\/10.1145\/2151171.2151182","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}