An algorithm based on SDP to solve distance calculation problem in OVFDM communication system

Author

Xiang, Wen ; Yang, Xing ; Fan, Lijun ; Shuai, Tianping ; Ai, Wenbao

Author_Institution

Sch. of Sci., Beijing Univ. of Posts & Telecommun., Beijing, China

fYear

2010

fDate

24-26 Sept. 2010

Firstpage

589

Lastpage

594

Abstract

An approximate algorithm, which is used to solve distance calculation problem in overlapped frequency division multiplexing (OVFDM) communication system, is presented in this paper. The distance calculation problem in OVFDM system is a {-2, 0, 2} combinatorial optimization problem. It is NP-hard. Our approximate algorithm for this problem uses the semi-definite relaxation method and rounding technique. So this algorithm is solvable in polynomial time and numerical results show that the algorithm is indeed efficient.

Keywords

combinatorial mathematics; computational complexity; frequency division multiplexing; optimisation; NP-hard problem; OVFDM communication system; combinatorial optimization problem; distance calculation problem; overlapped frequency division multiplexing; polynomial time; rounding technique; semidefinite relaxation; Algorithm design and analysis; Approximation algorithms; Approximation methods; Communication systems; OFDM; Search methods; Symmetric matrices; Distance Calculation; OVFDM; Rounding Technique; Semi-definite positive programming (SDP) relaxing;

fLanguage

English

Publisher

ieee

Conference_Titel

Network Infrastructure and Digital Content, 2010 2nd IEEE International Conference on

Conference_Location

Beijing

Print_ISBN

978-1-4244-6851-5

Type

conf

DOI

10.1109/ICNIDC.2010.5657849

Filename

5657849