  The Bandwidth Problem seeks for a simultaneous permutation of the rows and
columns of the adjacency matrix of a graph such that all nonzero entries are as
close as possible to the main diagonal. This work focuses on investigating
novel approaches to obtain lower bounds for the bandwidth problem. In
particular, we use vertex partitions to bound the bandwidth of a graph. Our
approach contains prior approaches for bounding the bandwidth as special cases.
By varying sizes of partitions, we achieve a trade-off between quality of
bounds and efficiency of computing them. To compute lower bounds, we derive a
Semidefinite Programming relaxation. We evaluate the performance of our
approach on several data sets, including real-world instances.
