Name
Abstract | ||
|---|---|---|
In this paper, we study the inapproximability of the following NP-complete number theoretic optimization problems introduced by Rossner and Seifert [C. Rossner, 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 a"1,...,a"n@?Z, find an @?"~-minimum GCD multiplier for a"1,...,a"n, i.e., a vector x@?Z^n with minimum max"1"@?"i"@?"n|x"i| satisfying @?"i"="1^nx"ia"i=gcd(a"1,...,a"n). We show that assuming PNP, it is NP-hard to approximate the Minimum GCD Multiplier in @?"~ norm (GCDM"~) within a factor n^c^/^l^o^g^l^o^g^n for some constant c0 where n is the dimension of the given vector. This improves on the best previous result. The best result so far gave 2^(^l^o^g^n^)^^^1^^^-^^^@e factor hardness by Rossner and Seifert [C. Rossner, 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 @e0 is an arbitrarily small constant. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2007.09.030 | Theoretical Computer Science |
Keywords | DocType | Volume |
greatest common divisor computation,n number,approximate optimum,best result,International Algorithmic Number Theory,factor n,J.P. Seifert,minimum GCD multiplier,C. Rossner,factor hardness | Journal | 396 |
Issue | ISSN | Citations |
1-3 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenbin Chen | 1 | 4 | 2.19 |
| Jiangtao Meng | 2 | 4 | 2.19 |
| Dengpan Yin | 3 | 46 | 3.64 |