{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T14:10:04Z","timestamp":1737123004085,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438663"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-45471-3_31","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T17:18:22Z","timestamp":1179767902000},"page":"298-307","source":"Crossref","is-referenced-by-count":0,"title":["Approximability of Dense Instances of Nearest Codeword Problem"],"prefix":"10.1007","author":[{"given":"1Cristina","family":"Bazgan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W. Fernandez","family":"Vega","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern and Z. Sweedyk, The Hardness of Approximate Optima in Lattice, Codes, and Systems of Linear Equations, Proc. of 34th IEEE FOCS, 1993, 724\u2013733.","DOI":"10.1109\/SFCS.1993.366815"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, D. Karger and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-hard Problems, Proc. of 27th ACM STOC, 1995, 284\u2013293; the full paper appeared in Journal of Computer and System Sciences 58 (1999), 193\u2013210.","DOI":"10.1006\/jcss.1998.1605"},{"key":"31_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-48321-7_6","volume-title":"Proc. Fundamentals of Computation Theory","author":"C. Bazgan","year":"1999","unstructured":"C. Bazgan and W. Fernandez de la Vega, A Polynomial Time Approximation Scheme for Dense Min 2Sat, Proc. Fundamentals of Computation Theory, LNCS 1684, Springer, 1999, 91\u201399."},{"key":"31_CR4","unstructured":"C. Bazgan, W. Fernandez de la Vega and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction, ECCC Technical Report TR01-034, 2001."},{"key":"31_CR5","unstructured":"P. Berman and M. Karpinski, Approximating Minimum Unsatisfiability of Linear Equations, Proc. 13th ACM-SIAM SODA, 2002, 514\u2013516."},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"A.E.F. Clementi and L. Trevisan, Improved Non-Approximability Results for Vertex Cover with Density Constraints, Proc. of 2nd Conference on Computing and Combinatorics, 1996, Springer, 1996, 333\u2013342.","DOI":"10.1007\/3-540-61332-3_167"},{"key":"31_CR7","unstructured":"I. Dinur, G. Kindler, R. Raz and S. Safra, An Improved Lower Bound for Approximating CVP, 2000, submitted."},{"key":"31_CR8","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"},{"issue":"3","key":"31_CR9","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U","volume":"8","author":"W. F. Vega de la","year":"1996","unstructured":"W. Fernandez de la Vega, Max-Cut Has a Randomized Approximation Scheme in Dense Graphs, Random Structures and Algorithms, 8(3) (1996), 187\u2013198.","journal-title":"Random Structures and Algorithms"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0020-0190(99)00048-4","volume":"70","author":"W. F. Vega de la","year":"1999","unstructured":"W. Fernandez de la Vega and M. Karpinski, On Approximation Hardness of Dense TSP and Other Path Problem, Information Processing Letters 70, 1999, 53\u201355.","journal-title":"Information Processing Letters"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"J. Hastad, Some Optimal Inapproximability Results, Proc. of 29th ACM STOC, 1997, 1\u201310.","DOI":"10.1145\/258533.258536"},{"issue":"301","key":"31_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.2307\/2282952","volume":"58","author":"W. Hoeffding","year":"1964","unstructured":"W. Hoeffding, Probability Inequalities for Sums of Bounded Random Variables, Journal of the American Statistical Association, 58(301), 1964, 13\u201330.","journal-title":"Journal of the American Statistical Association"},{"key":"31_CR13","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M. Karpinski","year":"1997","unstructured":"M. Karpinski, Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems, Randomization and Approximation Techniques in Computer Science, LNCS 1269, Springer, 1997, 1\u201314."},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"M. Karpinski and A. Zelikovsky, Approximating Dense Cases of Covering Problems, ECCC Technical Report TR 97-004, 1997, appeared also in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 40, 1998, 169-178.","DOI":"10.1090\/dimacs\/040\/11"},{"key":"31_CR15","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"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT 2002"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45471-3_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T14:39:22Z","timestamp":1737038362000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45471-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540438663"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-45471-3_31","relation":{},"subject":[]}}