On duality gap in binary quadratic programming

On duality gap in binary quadratic programming

0.00 Avg rating0 Votes
Article ID: iaor20124141
Volume: 53
Issue: 2
Start Page Number: 255
End Page Number: 269
Publication Date: Jun 2012
Journal: Journal of Global Optimization
Authors: , , ,
Keywords: programming: quadratic
Abstract:

We investigate in this paper the duality gap between the binary quadratic optimization problem and its semidefinite programming relaxation. We show that the duality gap can be underestimated by ξ r + 1 δ 2 equ1 , where δ is the distance between {-1, 1} n and certain affine subspace, and ξ r+1 is the smallest positive eigenvalue of a perturbed matrix. We also establish the connection between the computation of δ and the cell enumeration of hyperplane arrangement in discrete geometry.

Reviews

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