{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:33:52Z","timestamp":1774370032360,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540438649","type":"print"},{"value":"9783540454656","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_53","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"623-632","source":"Crossref","is-referenced-by-count":13,"title":["Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"53_CR1","first-page":"399","volume-title":"Hardness of Approximations, in Approximation Algorithms for NP-Hard Problems","author":"S. Arora","year":"1995","unstructured":"S. Arora, C. Lund, Hardness of Approximations, in Approximation Algorithms for NP-Hard Problems, D. S. Hochbaum (ed.), PWS Publishing, Boston 1995, 399\u2013446."},{"key":"53_CR2","unstructured":"C. Bazgan, W. Fernandez de la Vega and M. Karpinski, Approximability of dense instances of NEAREST CODEWORD problem, ECCC Tech. Report TR00-091, 2000, to appear in Proc. 8th SWAT (2002)."},{"key":"53_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Proc. of 26th ICALP","author":"P. Berman","year":"1999","unstructured":"P. Berman and M. Karpinski, On some tighter inapproximability results, Proc. of 26th ICALP, LNCS 1644, Springer-Verlag, Berlin, 1999, 200\u2013209."},{"key":"53_CR4","unstructured":"P. Berman and M. Karpinski, Approximating Minimum Unsatisfiability of Linear Equations, ECCC Technical Report, TR01-025, 2001, also in Proc. 13th ACM-SIAM SODA (2002), 514\u2013516."},{"key":"53_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(92)90140-Q","volume":"42","author":"T. N. Bui","year":"1992","unstructured":"T. N. Bui and C. Jones, Finding Good Approximate Vertex and Edge Partitions is Hard, Inform. Process. Letters 42 (1992), 153\u2013159.","journal-title":"Inform. Process. Letters"},{"key":"53_CR6","first-page":"407","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber and Z. Galil, Explicit construction of linear size superconcentrators, JCSS 22(1981), 407\u2013420.","journal-title":"JCSS"},{"key":"53_CR7","doi-asserted-by":"crossref","unstructured":"I. Dinur, G. Kindler and S. Safra, Approximating CVP to within almost polynomial factors is NP-hard, Proc. of 39th IEEE FOCS, 1998, 99\u2013109.","DOI":"10.1109\/SFCS.1998.743433"},{"key":"53_CR8","unstructured":"I. Dinur, G. Kindler, R. Raz and S. Safra, An improved lower bound for approximating CVP, 2000, submitted."},{"key":"53_CR9","doi-asserted-by":"crossref","unstructured":"U. Feige and R. Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, Proc. 41st IEEE FOCS (2000), pp. 105\u2013115.","DOI":"10.1109\/SFCS.2000.892070"},{"key":"53_CR10","doi-asserted-by":"crossref","unstructured":"S. Khanna, M. Sudan and L. Trevisan, Constraint Satisfaction: the approximability of minimization problems, Proc. of 12th IEEE Computational Complexity 1997, 282\u2013296.","DOI":"10.1109\/CCC.1997.612323"},{"key":"53_CR11","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica, 8 (1988), 261\u2013277.","journal-title":"Combinatorica"},{"key":"53_CR12","first-page":"425","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes, JCSS 43, 1991, pp. 425\u2013440.","journal-title":"JCSS"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:27:01Z","timestamp":1737052021000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_53","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}