DocumentCode :
3025940
Title :
Polynomial time solvable algorithms to binary quadratic programming problems with Q being a tri-diagonal or five-diagonal matrix
Author :
Gu, Shenshen
Author_Institution :
Sch. of Mechatron. Eng. & Autom., Shanghai Univ., Shanghai, China
fYear :
2010
fDate :
21-23 Oct. 2010
Firstpage :
1
Lastpage :
5
Abstract :
In the field of signal processing, many problems can be formulated as optimization problems. And most of these optimization problem can be further described in a formal form, that is binary quadratic programming problem(BQP). However, solving the BQP is proved to be NP-hard. Due to this reason, many novel algorithms have been proposed in order to improve the efficiency to solve the BQP. In this paper, polynomial algorithms to binary quadratic programming problems with Q being a tri-diagonal or five-diagonal matrix is focused by taking advantage of the basic algorithm proposed in. The basic algorithm is firstly reviewed and then this algorithm is modified to solve binary quadratic programming problems with Q being a tri-diagonal. Furthermore, by improving this algorithm, an algorithm is proposed to solve binary quadratic programming problems with Q being a five-diagonal matrix.
Keywords :
computability; computational complexity; matrix algebra; quadratic programming; signal processing; NP-hard; binary quadratic programming problem; five-diagonal matrix; optimization problem; polynomial time solvable algorithm; signal processing; tri-diagonal matrix; Polynomials; Programming; Quadratic programming; Signal processing; Signal processing algorithms; Symmetric matrices;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Wireless Communications and Signal Processing (WCSP), 2010 International Conference on
Conference_Location :
Suzhou
Print_ISBN :
978-1-4244-7556-8
Electronic_ISBN :
978-1-4244-7554-4
Type :
conf
DOI :
10.1109/WCSP.2010.5632199
Filename :
5632199
Link To Document :
بازگشت