Chen, Wenbin; Peng, Lingxi; Wang, Jianxiong; Li, Fufang; Tang, Maobin; Xiong, Wei; Wang, Songtao Inapproximability results for the minimum integral solution problem with preprocessing over \(\ell_{\infty}\) norm. (English) Zbl 1281.68121 Theor. Comput. Sci. 478, 127-131 (2013). Summary: The Minimum Integral Solution Problem with preprocessing has been introduced by M. Alekhnovich et al. [“Hardness of approximating the closest vector problem with preprocessing”, in: Proceedings of the 46th annual IEEE symposium on foundations of computer science, FOCS 2005. Los Alamitos: IEEE Computer Society. 216–225 (2005)]. They studied the complexity of Minimum Integral Solution Problem with preprocessing over \(\ell _{p}\) norm \((1\leq p<\infty )\). They leave an open problem about the complexity of the Minimum Integral Solution Problem with preprocessing over \(\ell_{\infty }\) norm. In this paper, we settle the problem. We show that the Minimum Integral Solution Problem with preprocessing over \(\ell_{\infty }\) norm (MISPP\(_{\infty }\)) is NP-hard to approximate to within a factor of \(\sqrt{2}-\varepsilon \) for any \(\varepsilon >0\), unless \(\mathrm{P}=\mathrm{NP}.\) Cited in 2 Documents MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Keywords:minimum integral solution problem; computational complexity; NP-hardness; PCP PDFBibTeX XMLCite \textit{W. Chen} et al., Theor. Comput. Sci. 478, 127--131 (2013; Zbl 1281.68121) Full Text: DOI