{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T19:27:13Z","timestamp":1743017233587,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_54","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"662-673","source":"Crossref","is-referenced-by-count":4,"title":["On the Hardness of Losing Weight"],"prefix":"10.1007","author":[{"given":"Andrei","family":"Krokhin","sequence":"first","affiliation":[]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10472-005-0419-3","volume":"43","author":"P. Chapdelaine","year":"2005","unstructured":"Chapdelaine, P., Creignou, N.: The complexity of Boolean constraint satisfaction local search problems. Annals of Mathematics and Artificial Intelligence\u00a043, 51\u201363 (2005)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"54_CR2","volume-title":"Handbook of Constraint Programming, ch.\u00a08","author":"D. Cohen","year":"2006","unstructured":"Cohen, D., Jeavons, P.: The complexity of constraint languages. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, ch.\u00a08. Elsevier, Amsterdam (2006)"},{"key":"54_CR3","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07 (2001)","DOI":"10.1137\/1.9780898718546"},{"issue":"1","key":"54_CR4","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0304-3975(01)00146-3","volume":"288","author":"P. Crescenzi","year":"2002","unstructured":"Crescenzi, P., Rossi, G.: On the Hamming distance of constraint satisfaction problems. Theoretical Computer Science\u00a0288(1), 85\u2013100 (2002)","journal-title":"Theoretical Computer Science"},{"key":"54_CR5","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic $(2-\\frac{2}{k+1})^n$ algorithm for k-SAT based on local search. Theoretical Computer Science\u00a0289, 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"key":"54_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Fellows, M.R.: Parameterized complexity: new developments and research frontiers. In: Aspects of Complexity (Kaikura, 2000). de Gruyter Series in Logic and Applications, vol.\u00a04, pp. 51\u201372 (2001)","DOI":"10.1515\/9783110889178.51"},{"key":"54_CR8","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"54_CR9","volume-title":"Algorithms for the Satisfiability Problem","author":"J. Gu","year":"2000","unstructured":"Gu, J., Purdom, P., Franko, J., Wah, B.W.: Algorithms for the Satisfiability Problem. Cambridge University Press, Cambridge (2000)"},{"key":"54_CR10","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1023\/A:1006318521185","volume":"24","author":"E. Hirsch","year":"2000","unstructured":"Hirsch, E.: SAT local search algorithms: worst-case study. Journal of Automated Reasoning\u00a024, 127\u2013143 (2000)","journal-title":"Journal of Automated Reasoning"},{"key":"54_CR11","volume-title":"Handbook of Constraint Programming, ch. 5","author":"H. Hoos","year":"2006","unstructured":"Hoos, H., Tsang, E.: Local search methods. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming. ch. 5. Elsevier, Amsterdam (2006)"},{"key":"54_CR12","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/S0890-5401(03)00037-3","volume":"187","author":"L. Kirousis","year":"2003","unstructured":"Kirousis, L., Kolaitis, P.: The complexity of minimal satisfiability problems. Information and Computation\u00a0187, 20\u201339 (2003)","journal-title":"Information and Computation"},{"key":"54_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00037-005-0195-9","volume":"14","author":"D. Marx","year":"2005","unstructured":"Marx, D.: Parameterized complexity of constraint satisfaction problems. Computational Complexity\u00a014, 153\u2013183 (2005)","journal-title":"Computational Complexity"},{"key":"54_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.orl.2007.02.008","volume":"36","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Searching the k-change neighborhood for TSP is W[1]-hard. Operations Research Letters\u00a036, 31\u201336 (2008)","journal-title":"Operations Research Letters"},{"key":"54_CR15","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:30:00Z","timestamp":1714620600000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}