On the $\Omega (n)$ SDP relaxation gap for Submodular Box-Constrained Quadratic Programming

Junyu Zhang, Guanyi Wang

Continuous submodular optimization is an important class of nonconvex problems with global guarantees, for which the submodular box-constrained quadratic programming (BCQP) forms a…