Lower Bounds for the Bandwidth Problem

The bandwidth problem asks 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 diagonal. We present novel approaches to obtain lower bounds on  the  bandwidth  problem  and  introduce  a  vertex  partition problem to bound the bandwidth of a graph. By varying sizesof partitions, we have a trade-off between quality of bounds and efficiency of computing them. To compute lower bounds, we  derive  several  SDP  relaxations.  Finally,  we  evaluate  our approach on a carefully selected set of benchmark instances.