Inapproximability results for the minimum integral solution problem with preprocessing over l(infinity) 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 l(p) norm (1 <= p < infinity). They leave an open problem about the complexity of the Minimum Integral Solution Problem with preprocessing over l(infinity) norm. In this paper, we settle the problem. We show that the Minimum Integral Solution Problem with preprocessing over l(infinity) norm (MISPP infinity) is NP-hard to approximate to within a factor of root 2 - epsilon for any epsilon > 0, unless P = NP.

关键词