{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,14]],"date-time":"2025-07-14T02:31:05Z","timestamp":1752460265304},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_85","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:53:38Z","timestamp":1330260818000},"page":"461-472","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximation of Constraint Satisfaction via local search"],"prefix":"10.1007","author":[{"given":"Hoong Chuin","family":"Lau","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Edoardo Amaldi and Viggo Kann. On the approximability of finding maximum feasible subsystems of linear systems. In Proc. STACS 94, pp. 521\u2013532, 1994.","DOI":"10.1007\/3-540-57785-8_168"},{"key":"40_CR2","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman and G. Schnitger. On the complexity of approximating the independent set problem. Infor. & Comput., Vol. 96, pp. 77\u201394, 1992.","journal-title":"Infor. & Comput."},{"key":"40_CR3","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R. L. Brooks","year":"1941","unstructured":"R. L. Brooks. On colouring the nodes of a network. In Proc. Cambridge Philos. Soc., Vol. 37, pp. 194\u2013197, 1941.","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0012-365X(78)90049-3","volume":"22","author":"P. Catlin","year":"1978","unstructured":"Paul Catlin. A bound on the chromatic number of a graph. Discrete Math., Vol. 22, pp. 81\u201383, 1978.","journal-title":"Discrete Math."},{"key":"40_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R. Dechter","year":"1988","unstructured":"Rina Dechter and Judea Pearl. Network-based heuristics for constraint satisfaction. Artif. Int., Vol. 34, pp. 1\u201338, 1988.","journal-title":"Artif. Int."},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Michel X. Goemans and David P. Williamson. Approximation algorithms for MAX CUT and MAX 2SAT. In Proc. STOC 94, pp. 422\u2013431, 1994.","DOI":"10.1145\/195058.195216"},{"key":"40_CR7","unstructured":"Magn\u00fas M. Halld\u00f3rsson. 1994. Personal communication."},{"key":"40_CR8","unstructured":"Magn\u00fas M. Halld\u00f3rsson. Approximating discrete collections via local improvements. In Proc. SODA 95, pp. 601\u2013610, San Francisco, California, January 1995."},{"key":"40_CR9","unstructured":"S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability. In Proc. FOCS 94, 1994."},{"key":"40_CR10","first-page":"237","volume":"1","author":"L. Lov\u00e1sz","year":"1966","unstructured":"L. Lov\u00e1sz. On decomposition of graphs. Studia Sci. Math. Hungar., Vol. 1, pp. 237\u2013238, 1966.","journal-title":"Studia Sci. Math. Hungar."},{"key":"40_CR11","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Sys. Sci., Vol. 43, pp. 425\u2013440, 1991.","journal-title":"J. Comput. Sys. Sci."},{"issue":"3","key":"40_CR12","doi-asserted-by":"crossref","first-page":"519","DOI":"10.4153\/CJM-1982-036-8","volume":"34","author":"S. Poljak","year":"1982","unstructured":"Svatopluk Poljak and Daniel Turzik. A polynomial time algorithm for constructing a large bipartite subgraph, with an application to a satisfiability problem. Can. J. Math, Vol. 34, No. 3, pp. 519\u2013524, 1982.","journal-title":"Can. J. Math"},{"issue":"1","key":"40_CR13","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/0220004","volume":"20","author":"A. A. Schaffer","year":"1991","unstructured":"Alejandro A. Schaffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM J. Comput., Vol. 20, No. 1, pp. 56\u201387, 1991.","journal-title":"SIAM J. Comput."},{"key":"40_CR14","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0012-365X(81)90023-6","volume":"34","author":"P. Vitanyi","year":"1981","unstructured":"Paul Vitanyi. How well can a graph be n-colored? Discrete Math., Vol. 34, pp. 69\u201380, 1981.","journal-title":"Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_85","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T21:18:38Z","timestamp":1578518318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_85"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_85","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}