Spectral bounds for the maximum cut problem

The maximum cut problem is a classical combinatorial optimization problem that is known to be NP-hard in general. In the present article, we provide some new lower and upper bounds that are based on the eigenvalues of the weight matrix with modified diagonal entries. Namely, we show that some upper bounds presented here are generally better than the SDP bound introduced by Goemans and Williamson, JACM 42 (1995), 1115-1145. We also discuss the complexity of computing these bounds and provide some preliminary computational results.