Inapproximability results for the minimum integral solution problem with preprocessing over l(infinity) norm

作者：Chen Wenbin^*; Peng Lingxi; Wang Jianxiong; Li Fufang; Tang Maobin; Xiong Wei; Wang Songtao

来源：Theoretical Computer Science, 2013, 478: 127-131.

DOI：10.1016/j.tcs.2013.01.028

• Minimum integral solution problem
• Computational complexity
• NP-hardness
• PCP

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.

• 单位
  复旦大学; 广州大学; 华南师范大学; 南京大学