Inapproximability results for the minimum integral solution problem with preprocessing over ℓ∞ norm

The Minimum Integral Solution Problem with preprocessing has been introduced by Alekhnovich, Khot, Kindler, and Vishnoi [M. Alekhnovich, S. Khot, G. Kindler, N. Vishnoi, Hardness of approximating the closest vector problem with preprocessing, in: Proc. 46th IEEE Symposium on FOCS, 2005, pp. 216–225]. They studied the complexity of Minimum Integral Solution Problem with preprocessing over ℓp norm (1≤p<∞). They leave an open problem about the complexity of the Minimum Integral Solution Problem with preprocessing over ℓ∞ norm. In this paper, we settle the problem. We show that the Minimum Integral Solution Problem with preprocessing over ℓ∞ norm () is NP-hard to approximate to within a factor of for any ϵ>0, unless .