{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:59:24Z","timestamp":1725584364675},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,8,2]],"date-time":"2013-08-02T00:00:00Z","timestamp":1375401600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10878-013-9646-4","type":"journal-article","created":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T11:56:00Z","timestamp":1375358160000},"page":"447-455","source":"Crossref","is-referenced-by-count":4,"title":["An improved lower bound for approximating the Minimum Integral Solution Problem with Preprocessing over $$\\ell _\\infty $$ \u2113 \u221e norm"],"prefix":"10.1007","volume":"30","author":[{"given":"Wenbin","family":"Chen","sequence":"first","affiliation":[]},{"given":"Lingxi","family":"Peng","sequence":"additional","affiliation":[]},{"given":"Jianxiong","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Fufang","family":"Li","sequence":"additional","affiliation":[]},{"given":"Maobin","family":"Tang","sequence":"additional","affiliation":[]},{"given":"Wei","family":"Xiong","sequence":"additional","affiliation":[]},{"given":"Songtao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,8,2]]},"reference":[{"key":"9646_CR1","unstructured":"Ajtai M (1996) Generating hard instances of lattice problems. In: Proceedings of the 28th annual ACM symposium on theory of computing, pp 99\u2013108"},{"key":"9646_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich M, Khot S, Kindler G, Vishnoi N (2005) Hardness of approximating the closest vector problem with pre-processing. In: Proceedings of the 46th IEEE symposium on FOCS, pp 216\u2013225","DOI":"10.1109\/SFCS.2005.40"},{"key":"9646_CR3","unstructured":"Arora S (1994) Probabilistic checking of proofs and the hardness of approximation problems. PhD Thesis, UC Berkeley"},{"key":"9646_CR4","doi-asserted-by":"crossref","unstructured":"Arora S, Babai L, Stern J, Sweedyk EZ (1997) The hardness of approximate optima in lattices, codes, and systems of linear equations. J Comput Syst Sci 54(2):317\u2013331","DOI":"10.1006\/jcss.1997.1472"},{"key":"9646_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"G Ausiello","year":"1995","unstructured":"Ausiello G, Crescenzi P, Protasi M (1995) Approximation solutions of NP-optimization problems. Theor Comput Sci 150:1\u201355","journal-title":"Theor Comput Sci"},{"key":"9646_CR6","unstructured":"Bellare M, Goldwasser S, Lund C, Russel A (1993) Efficient probabilistically checkable proofs with applications to approximation problems. In: Proceedings of the 25th ACM symposium on theory of computing, pp 294\u2013304"},{"key":"9646_CR7","volume-title":"Combinatorics","author":"B Bollob\u00e1s","year":"1986","unstructured":"Bollob\u00e1s B (1986) Combinatorics. Cambridge University Press, Cambridge"},{"issue":"2","key":"9646_CR8","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1109\/18.52484","volume":"36","author":"J Bruck","year":"1990","unstructured":"Bruck J, Naor M (1990) The hardness of decoding linear codes with preprocessing. IEEE Trans Inf Theory 36(2):381\u2013385","journal-title":"IEEE Trans Inf Theory"},{"key":"9646_CR9","doi-asserted-by":"crossref","unstructured":"Chen W, Peng L, Wang J, Li F, Tang M, Xiong W, Wang S (2013) In approximability results for the minimum integral solution problem with preprocessing over infinity norm. Theor Comput Sci 478:127\u2013131","DOI":"10.1016\/j.tcs.2013.01.028"},{"issue":"10","key":"9646_CR10","doi-asserted-by":"crossref","first-page":"4603","DOI":"10.1109\/TIT.2006.881835","volume":"52","author":"WB Chen","year":"2006","unstructured":"Chen WB, Meng JT (2006) The hardness of the closest vector problem with preprocessing over $$\\ell _\\infty $$ \u2113 \u221e norm. IEEE Trans Inf Theory 52(10):4603\u20134606","journal-title":"IEEE Trans Inf Theory"},{"issue":"1\u20133","key":"9646_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2007.09.030","volume":"396","author":"W Chen","year":"2008","unstructured":"Chen W, Meng J, Yin D (2008) An improved lower bound for approximating minimum GCD multiplier in $$\\ell _\\infty $$ \u2113 \u221e norm (GCDM $$_\\infty $$ \u221e ). Theor Comput Sci 396(1\u20133):1\u20139","journal-title":"Theor Comput Sci"},{"key":"9646_CR12","doi-asserted-by":"crossref","unstructured":"Dinur I (2000) Approximating SVP $$_\\infty $$ \u221e to within almost-polynomial factors is NP-hard. In: Proceedings of the 4th Italian conference on algorithms and complexity. LNCS, vol 1767. Springer, Berlin","DOI":"10.1007\/3-540-46521-9_22"},{"issue":"2","key":"9646_CR13","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s00493-003-0019-y","volume":"23","author":"I Dinur","year":"2003","unstructured":"Dinur I, Kindler G, Raz R, Safra S (2003) Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica 23(2):205\u2013243","journal-title":"Combinatorica"},{"key":"9646_CR14","doi-asserted-by":"crossref","unstructured":"Feige U, Micciancio D (2004) The inapproximability of lattice and coding problems with preprocessing. J Comput Syst Sci 69(1):45\u201367","DOI":"10.1016\/j.jcss.2004.01.002"},{"issue":"2","key":"9646_CR15","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U Feige","year":"1996","unstructured":"Feige U, Goldwasser S, Lov\u00e1sz L, Safra S, Szegedy M (1996) Interactive proofs and the hardness of approximating cliques. J ACM 43(2):268\u2013292","journal-title":"J ACM"},{"key":"9646_CR16","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory NP-completeness. W. H. Freeman and Company, San Francisco"},{"issue":"4","key":"9646_CR17","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1109\/18.53763","volume":"36","author":"A Lobstein","year":"1990","unstructured":"Lobstein A (1990) The hardness of solving subset sum with preprocessing. IEEE Trans Inf Theory 36(4):943\u2013946","journal-title":"IEEE Trans Inf Theory"},{"key":"9646_CR18","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1109\/18.915688","volume":"47","author":"D Micciancio","year":"2001","unstructured":"Micciancio D (2001) The hardness of the closest vector problem with preprocessing. IEEE Trans Inf Theory 47:1212\u20131215","journal-title":"IEEE Trans Inf Theory"},{"key":"9646_CR19","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1109\/CCC.2003.1214435","volume":"18","author":"O Regev","year":"2003","unstructured":"Regev O (2003) Improved inapproximability of lattice and coding problem with preprocessing. Proc Annu IEEE Conf Comput Complex 18:363\u2013370","journal-title":"Proc Annu IEEE Conf Comput Complex"},{"key":"9646_CR20","doi-asserted-by":"crossref","unstructured":"Regev O, Rosen R (2006) Lattice problems and norm embeddings. In: Proceedings of STOC","DOI":"10.1145\/1132516.1132581"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9646-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9646-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9646-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T05:42:51Z","timestamp":1563601371000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9646-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,2]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["9646"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9646-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8,2]]}}}