In recent years, there have been intensive research on algorithmic
development for binary quadratic programming problems (BQP) based on
advanced convex optimization relaxations such as semidefinite
programming (SDP). However, these approaches are usually restricted
to moderately sized problems due to the capacity of the underlying SDP solvers.

In this talk, we reconsider a classical simple convex quadratic
programming relaxation for the underlying BQP and
recast it as a second order conic optimization relaxation. Such
a reformulation allows us to use graph modeling techniques to improve
the relaxation model. Secondly, we use the convex
quadratic relaxation as a geometric embedding tool to reformulate a
specific class of BQPs, the densest k-subgraph problem, as a
clustering problem where the target is to find a single cluster of
fixed size. A simple 2-approximation algorithm for the clustering
problem is proposed. Numerical results based on the new
relaxation model and the proposed algorithm will be reported.


The work is supported by AFOSR grant FA9550-09-1-0098.