A New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph

摘要

Binary quadratic programming (BQP) problem was an NP-hard problem and had a large number of applications. In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem. Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation. When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation. Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.