graph partition – Optimization Online

Lower Bounds for the Bandwidth Problem

Published: 2019/04/12

Semi-definite Programming bandwidth problem, graph partition, semidefinite programming

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 main diagonal. This work focuses on investigating novel approaches to obtain lower bounds for the bandwidth problem. In particular, we use vertex partitions … Read more

An efficient semidefinite programming relaxation for the graph partition problem

Published: 2011/08/09, Updated: 2012/09/02

Renata Sotirov

Semi-definite Programming graph equipartition, graph partition, matrix lifting, semidefinite programming, vector lifting

We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation [A. Frieze and M. Jerrum. Improved approximation algorithms for … Read more