A linearithmic time algorithm for a shortest vector problem in compute-and-forward design
Authors:
- 11 August 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2344-2348
Abstract
We modify the algorithm proposed by Sahraei et al. in 2015, resulting an algorithm with expected complexity of O(n log n) arithmetic operations to solve a special shortest vector problem arising in computer-and-forward design, where n is the dimension of the channel vector. This algorithm is more efficient than the best known algorithms with proved complexity.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- An Efficient Algorithm for Optimally Solving a Shortest Vector Problem in Compute-and-Forward DesignIEEE Transactions on Wireless Communications, 2016
- Compute-and-forward protocol design based on improved sphere decoding2015
- Compute-and-Forward: Finding the best equation2014
- A quadratic programming relaxation approach to compute-and-forward network coding design2014
- An efficient branch-and-bound algorithm for compute-and-forward2012
- On the ergodic rate for compute-and-forward2012
- Compute-and-Forward: Harnessing Interference Through Structured CodesIEEE Transactions on Information Theory, 2011
- Algorithms for the Shortest and Closest Lattice Vector Problems2011
- The shortest vector problem in L 2 is NP -hard for randomized reductions (extended abstract)1998
- Lattice basis reduction: Improved practical algorithms and solving subset sum problemsMathematical Programming, 1994