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

DOI

10.2991/mmsa-18.2018.70How to use a DOI?

Keywords

binary quadratic programming; doubly nonnegative relaxation; semidefinite relaxation; densest k-subgraph

Abstract

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.

Copyright

© 2018, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Chuanhao Guo
AU  - Liping Tang
PY  - 2018/03
DA  - 2018/03
TI  - A New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph
BT  - Proceedings of the 2018 International Conference on Mathematics, Modelling, Simulation and Algorithms (MMSA 2018)
PB  - Atlantis Press
SP  - 314
EP  - 320
SN  - 1951-6851
UR  - https://doi.org/10.2991/mmsa-18.2018.70
DO  - 10.2991/mmsa-18.2018.70
ID  - Guo2018/03
ER  -