×

Inapproximability results for the minimum integral solution problem with preprocessing over \(\ell_{\infty}\) norm. (English) Zbl 1281.68121

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}.\)

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI