Given an n-dimensional lattice L and some target vector, this paper studies the algorithms for approximate closest vector problem （CVPγ） by using an approximate shortest independent vectors problem oracle （SIVPγ...Given an n-dimensional lattice L and some target vector, this paper studies the algorithms for approximate closest vector problem （CVPγ） by using an approximate shortest independent vectors problem oracle （SIVPγ）. More precisely, if the distance between the target vector and the lattice is no larger than c/γn λ1（L） for arbitrary large but finite constant c 〉 0, we give randomized and deterministic polynomial time algorithms to find a closest vector, while previous reductions were only known for 1/2γn λ1（L）. Moreover, if the distance between the target vector and the lattice is larger than some quantity with respect to λn（L）, using SIVPγ oracle and Babai＇s nearest plane algorithm, we can solve CVPγ√n in deterministic polynomial time. Specially, if the approximate factor γ ∈ （1, 2） in the SIVPγ oracle, we obtain a better reduction factor for CVP.展开更多
The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.
基金This work is partially supported by the National Basic Research 973 Program of China under Grant No. 2011CB302400, the National Natural Science Foundation of China under Grant Nos. 61379139 and 61133013, and the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No. XDA06010701.
文摘Given an n-dimensional lattice L and some target vector, this paper studies the algorithms for approximate closest vector problem （CVPγ） by using an approximate shortest independent vectors problem oracle （SIVPγ）. More precisely, if the distance between the target vector and the lattice is no larger than c/γn λ1（L） for arbitrary large but finite constant c 〉 0, we give randomized and deterministic polynomial time algorithms to find a closest vector, while previous reductions were only known for 1/2γn λ1（L）. Moreover, if the distance between the target vector and the lattice is larger than some quantity with respect to λn（L）, using SIVPγ oracle and Babai＇s nearest plane algorithm, we can solve CVPγ√n in deterministic polynomial time. Specially, if the approximate factor γ ∈ （1, 2） in the SIVPγ oracle, we obtain a better reduction factor for CVP.
基金Acknowledgements This work was supported by the National Natural Science Foundation of China （Grant No. 11371138）.
文摘The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.
