Article ID: | iaor20107611 |
Volume: | 48 |
Issue: | 3 |
Start Page Number: | 497 |
End Page Number: | 508 |
Publication Date: | Nov 2010 |
Journal: | Journal of Global Optimization |
Authors: | Xing Wenxun, Wang Zhenbo, Lu Cheng |
This paper presents an improved lower bound and an approximation algorithm based on spectral decomposition for the binary constrained quadratic programming problem. To decompose spectrally the quadratic matrix in the objective function, we construct a low rank problem that provides a lower bound. Then an approximation algorithm for the binary quadratic programming problem together with a worst case performance analysis for the algorithm is provided.