{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:41:20Z","timestamp":1743007280171,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030271947"},{"type":"electronic","value":"9783030271954"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-27195-4_4","type":"book-chapter","created":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T09:03:14Z","timestamp":1564650194000},"page":"42-50","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Closest Vector Problem in $$\\ell _\\infty $$ Norm Revisited"],"prefix":"10.1007","author":[{"given":"Wenbin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,1]]},"reference":[{"key":"4_CR1","unstructured":"Ajtai, M.: The shortest vector problem in $$L_{2}$$ is NP-hard for randomized reductions. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 10\u201319 (1998)"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 601\u2013610 (2001)","DOI":"10.1145\/380752.380857"},{"key":"4_CR3","unstructured":"Arora, S.: Probabilistic checking of proofs and the hardness of approximation problems. Ph.D. thesis, UC Berkeley (1994)"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, E.Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54, 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR5","unstructured":"Arora, S., Lund, C.: Hardness of approximations. In: Approximation Algorithms for NP-Hard Problems. PWS Publishing (1996)"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"Babai, L.: On Lov\u00e1sz\u2019s lattice reduction and the nearest lattice point problem. Combinatorica 6, 1\u201314 (1986)","journal-title":"Combinatorica"},{"key":"4_CR7","volume-title":"Combinatorics","author":"B Bollob\u00e1s","year":"1986","unstructured":"Bollob\u00e1s, B.: Combinatorics. Cambridge University Press, Cambridge (1986)"},{"key":"4_CR8","unstructured":"Cai, J.Y., Nerurkar, A.: Approxiamting the SVP to within a factor $$(1+1\/dim^{\\epsilon })$$ is NP-hard under randomizied reductions. In: Proceedings of the 13th Annual IEEE Conference on Computational Complexity, pp. 151\u2013158 (1998)"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/3-540-46521-9_22","volume-title":"Algorithms and Complexity","author":"I Dinur","year":"2000","unstructured":"Dinur, I.: Approximating SVP$$_{\\infty }$$ to within almost-polynomial factors is NP-hard. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 263\u2013276. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-46521-9_22"},{"key":"4_CR10","unstructured":"Dinur, I., Kindler, G., Safra, S.: Approximating CVP to within almost-polynomial factors is NP-hard. In: Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (1998)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Gauss, C.F.: Disquisitiones arithmeticae. (leipzig 1801), art. 171. Yale University Press. English Translation by A.A. Clarke (1966)","DOI":"10.5479\/sil.324926.39088000932822"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/3-540-48340-3_10","volume-title":"Mathematical Foundations of Computer Science 1999","author":"G Havas","year":"1999","unstructured":"Havas, G., Seifert, J.-P.: The complexity of the extended GCD problem. In: Kuty\u0142owski, M., Pacholski, L., Wierzbicki, T. (eds.) MFCS 1999. LNCS, vol. 1672, pp. 103\u2013113. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48340-3_10"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Kannan, R.: Improved algorithm for integer programming and related lattice problems. In: Proceedings of the 15 Annual ACM Symposium on Theory of Computing, pp. 193\u2013206 (1983)","DOI":"10.1145\/800061.808749"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12, 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"4_CR15","unstructured":"Kannan, R., Sudun, M., Trevisan, L.: Constraint satisfaction: the approximability of minimization problems. In: Proceedings of the 12th IEEE Conference of Computational Complexity, pp. 282\u2013296 (1997)"},{"key":"4_CR16","unstructured":"Khot, S.: Hardness of approximating the shortest vector problem in high $$L_p$$ norms. In: Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (2003)"},{"key":"4_CR17","unstructured":"Khot, S.: Hardness of approximating the shortest vector problem in lattices. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (2004)"},{"issue":"3","key":"4_CR18","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/500559.500560","volume":"32","author":"R Kumar","year":"2001","unstructured":"Kumar, R., Sivakumar, D.: Complexity of SVP-A reader\u2019s digest. SIGACT News 32(3), 40\u201352 (2001). Complexity Theory Column (ed. L.Hemaspaandra)","journal-title":"SIGACT News"},{"issue":"1","key":"4_CR19","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"JC Lagarias","year":"1985","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. ACM 32(1), 229\u2013246 (1985)","journal-title":"J. ACM"},{"issue":"2","key":"4_CR20","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0022-0000(85)90013-3","volume":"30","author":"S Landau","year":"1985","unstructured":"Landau, S., Miller, G.L.: Solvability of radicals in polynomial time. J. Comput. Syst. Sci. 30(2), 179\u2013208 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR21","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Technical report 81-03, University of Amsterdam, Amsterdam (1981)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov$$\\acute{a}$$sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 513\u2013534 (1982)","DOI":"10.1007\/BF01457454"},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of minimizaiton problems. J. ACM 41, 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"4_CR24","unstructured":"Micciancio, D.: The shortest vector problem is NP-hard to approximate to within some constant. In: Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (1998)"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems, A Cryptographic Perspective. Klumer Academic Publishers (2002)","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"4_CR26","unstructured":"Minkowski, H.: Geometrie der zahlen. Leizpig, Tuebner (1910)"},{"key":"4_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/3-540-61581-4_64","volume-title":"Algorithmic Number Theory","author":"C R\u00f6ssner","year":"1996","unstructured":"R\u00f6ssner, C., Seifert, J.-P.: The complexity of approximate optima for greatest common divisor computations. In: Cohen, H. (ed.) ANTS 1996. LNCS, vol. 1122, pp. 307\u2013322. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61581-4_64"},{"key":"4_CR28","unstructured":"Schnorr, C.P.: A hierarchy of polynomial-time basis reduction algorithms. In: Proceedings of Conference on Algorithms, P$$\\acute{e}$$ecs (Hungary), pp. 375\u2013386 (1985)"},{"key":"4_CR29","unstructured":"van Emde Boas, P.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical report 81-04, Mathematische Instiut, University of Amsterdam (1981)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-27195-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:15:51Z","timestamp":1709824551000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-27195-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030271947","9783030271954"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-27195-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"1 August 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Applications in Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/theory.ict.ac.cn\/aaim2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}