title: Numerical Approaches for SDP Relaxations of the Max-Cut Problem Miguel Anjos, Serge Kruk, Henry Wolkowicz Dept. Comb. and Opt. University of Waterloo Abstract: We look at two strengthened semidefinite programming relaxations of the Max-Cut problems. We show that these strictly strengthen the well-known SDP relaxation. We then exploit the special sparsity structure and study empirical solutions for these relaxations.