1. Inapproximability results for the minimum integral solution problem with preprocessing over norm.
- Author
-
Chen, Wenbin, Peng, Lingxi, Wang, Jianxiong, Li, Fufang, Tang, Maobin, Xiong, Wei, and Wang, Songtao
- Subjects
- *
INTEGRALS , *APPROXIMATION theory , *CONFERENCES & conventions , *COMPUTATIONAL complexity - Abstract
Abstract: 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 norm . 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 , unless . [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF