Title :
Speed and accuracy comparison of techniques to solve a binary quadratic programming problem with applications to synchronous CDMA
Author :
Hasegawa, F. ; Luo, J. ; Pattipati, K. ; Willett, P.
Author_Institution :
Electr. & Comput. Eng. Dept., Connecticut Univ., Storrs, CT, USA
Abstract :
We compare methods for solving the NP-hard binary quadratic programming (BQP) problem. Various methods are discussed, including box-constrained quadratic programming, branch and bound, coordinate descent, group decision making and semi-definite relaxation. An algorithm from target-tracking, the probabilistic data association filter, is modified to the BQP application. Simulation results show that this and several other methods can significantly outperform the decision feedback detector (DFD) or its group counterpart, GDFD
Keywords :
code division multiple access; computational complexity; decision theory; discrete time filters; matrix algebra; probability; quadratic programming; tree searching; NP-hard problem; accuracy comparison; binary quadratic programming problem; box-constrained; branch and bound; coordinate descent; group decision making; probabilistic data association filter; semi-definite relaxation; speed comparison; synchronous CDMA; target tracking; Computer errors; Covariance matrix; Decorrelation; Design for disassembly; Detectors; Feedback; Matched filters; Multiaccess communication; Quadratic programming; Symmetric matrices;
Conference_Titel :
Decision and Control, 2001. Proceedings of the 40th IEEE Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-7061-9
DOI :
10.1109/.2001.980810
