van Dam, E.R.; Sotirov, R. - Tilburg University, School of Economics and Management - 2015
We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the min-cut problem. Our new semidefinite programming relaxation of the min-cut problem is obtained by strengthening the known semidefinite programming relaxation for the quadratic assignment problem...