NODE AND EDGE RELAXATIONS OF THE MAX-CUT PROBLEM

We study an upper bound on the max-cut problem defined via a relaxatio n of the discrete problem to a continuous nonlinear convex problem, wh ich can be solved efficiently. We demonstrate how far the approach can be pushed using advanced techniques from numerical linear algebra and nonsmooth optimization. Various classes of graphs with up to 50 000 n odes and up to four million edges are considered. Since the theoretica l bound can be computed only with a certain precision in practice, we use duality between node- and edge-oriented relaxations to estimate th e difference between the theoretical and the computed bounds.