On Polynomial-Factor Approximations to the Shortest Lattice Vector Length
Ravi Kumar, D. Sivakumar · SIAM Journal on Discrete Mathematics · 2003
For every constant $\epsilon > 0$, we obtain a $2^{O(n(1/2 + 1/\epsilon))}$ time randomized algorithm to approximate the length of the shortest vector in an n-dimensional lattice to within a factor of $n^{3 + \epsilon}$.