Given a graph G, the maximum cut problem consists of finding the subset S of vertices such that the number of edges having exactly one endpoint in S is as large as possible. In the weighted version of this problem there are given real weights on the edges of G, and the objective is to maximize the sum of the weights of the edges having exactly one endpoint in the subset S. In this paper the authors consider the maximum cut problem and some related problems, like maximum-2-satisfiability, weighted signed graph balancing. They describe the relation of these problems to the unconstrained quadratic 0-1 programming problem, and survey the known methods for lower and upper bounds to this optimization problem. The authors also give the relation between the related polyhedra, and they describe some of the known and some new classes of facets for them.
