Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward
Saeid Sahraei, Michael Gastpar · IEEE Transactions on Information Theory · 2017
A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψ log(nψ)), where ψ = √P∥h∥2+ 1 depends on the transmission power and the norm of the channel vector. We will then extend our results to integer-forcing and finally introduce a more general class of lattices for which the SVP and the closest vector problem can be approximated within a constant factor.