An improved lower bound for approximating minimum GCD multiplier in ℓ∞ norm ()

In this paper, we study the inapproximability of the following NP-complete number theoretic optimization problems introduced by Rössner and Seifert [C. Rössner, J.P. Seifert, The complexity of approximate optima for greatest common divisor computations, in: Proceedings of the 2nd International Algorithmic Number Theory Symposium, ANTS-II, 1996, pp. 307–322]:Given n numbers , find an ℓ∞-minimum GCD multiplier for a1,…,an, i.e., a vector with minimum max1≤i≤n|xi| satisfying .We show that assuming , it is NP-hard to approximate the Minimum GCD Multiplier in ℓ∞ norm () within a factor nc/loglogn for some constant c>0 where n is the dimension of the given vector. This improves on the best previous result. The best result so far gave 2(logn)1−ϵ factor hardness by Rössner and Seifert [C. Rössner, J.P. Seifert, The complexity of approximate optima for greatest common divisor computations, in: Proceedings of the 2nd International Algorithmic Number Theory Symposium, ANTS-II, 1996, pp. 307–322], where ϵ>0 is an arbitrarily small constant.