An improved lower bound and approximation algorithm for binary constrained quadratic programming problem

An improved lower bound and approximation algorithm for binary constrained quadratic programming problem

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.