Building upper bounds for graph partitioning problems

Graph partitioning is to partition the vertices of a  graph with the minimum

total weight for all the edges cut by the partition. It is an NP-hard

problem. Also, the computational expense of solving that problem by

heuristics gets huge when the graph size increases. This talk presents

heuristics to obtain tight lower bounds via the semidefinite programming

(SDP) relaxations. We solve the SDP relaxation at first and then build

feasible solutions based on the SDP solution. First numerical

experiments demonstrate that we find high-quality bounds at a reasonable

computational cost.