An improved lower bound for approximating the Minimum Integral Solution Problem with Preprocessing over norm

摘要

In this paper, we study the approximation complexity of the Minimum Integral Solution Problem with Preprocessing introduced by Alekhnovich et al. (FOCS, pp. 216-225, 2005). We show that the Minimum Integral Solution Problem with Preprocessing over norm () is NP-hard to approximate to within a factor of unless This improves on the best previous result. The best result so far gave factor hardness for any epsilon > 0.

关键词