Given an undirected graph G=(V,E), the MAXCUT problem is to partition the vertex set V
into two disjoint sets U and W so that the number of edges crossing the cut from U to W is maximized.
(An edge crosses the cut if it has one endpoint in U and one in W.)
A simple (1/2)approximation algorithm for this problem is:
 Choose a random subset U of V, let W=VU.
Then each edge has probability 1/2 of crossing the cut, so the expected
size of the cut is E/2. Since OPT ≤ E, this is a (1/2)approximation algorithm.
This was the best algorithm known until Goemans and Williamson gave a better performance guarantee
for an algorithm based on SemidefiniteProgramming .
Given an undirected graph G=(V,E) with n vertices, consider the following optimization problem:
EMBED:
 Embed the vertices of G on the surface of the unit sphere in ℜ^{n},
so as to maximize ∑_{u,v} [1y(u).y(v)]/2,
where y(v) denotes the point where vertex v is embedded.
Note: [1y(u).y(v)]/2 is the Euclidean distance between u and v, squared, over 4.
So the cost is the sum, over the edges, of the distances between the endpoints squared, over 4.
Examples:
 Let G = path of length 3.
 Let G = the triangle.
 Let G = 5cycle.
A feasible solution to EMBED is an embedding (assigning each vertex to a point on the sphere).
The cost of the solution is ∑_{u,v} [1y(u).y(v)]/2.
claim 1: This optimization problem is a relaxation of maxcut.
proof sketch:
 Prove that, for each cut in G, there is a feasible solution whose cost equals the size of the cut.
claim 2: This optimization problem can be solved in polynomial time using SDP.
proof sketch: Here is the corresponding SDP:
 maximize ∑_{u,v} [1X_{uv}]/2 subject to
 X_{uu} = 1 for each vertex u
 X is positive semidefinite.
 Each feasible solution to EMBED gives a feasible solution to the SDP: X_{uv} = y(u).y(v).
 Conversely, since X is positive semidefinite if and only if it can be expressed as X = Y^{T} Y,
 each feasible solution to the SDP gives a feasible solution to the SDP.
 The costs of the feasible solutions correspond.
The algorithm:
 Given the graph G with n vertices, compute y^{*}∈ℜ^{n}  the optimal embedding onto the unit sphere.
 Choose a random hyperplane in ℜ^{n} through the origin.
 Let U be the vertices v such that y(v) is on one side of the hyperplane, let W be the vertices on the other side.
thm: This is a .878approximation algorithm for MAXCUT.
Proof sketch:
 Consider a single edge (u,v) in the graph, with vertices embedded at y(u) and y(v) respectively.
 What is the probability that (u,v) crosses the cut? We claim this is at least .878*[1y(u).y(v)]/2.
 This proves the result because then the expected number of edges cut is at least
 .878 ∑_{uv} [1y(u).y(v)]/2, which is at least .878 OPT, because EMBED is a relaxation of MAXCUT.

 Let θ denote the angle between y(u) and y(v). That is, cos(theta) = y(u).y(v).
 Then the probability that y(u) and y(v) lie on opposite sides of the cut is 2θ/2π. (Draw a picture.)
 So, we need to show 2θ/2π ≥ .878 [1y(u).y(v)]/2 = .878 [ 1cos(θ)/2]..
 We leave this as an exercise.
References:
 Chapter 26 of Approximation Algorithms by Vijay Vazirani
 [M. Goemans and D. Williamson. A 0.878 approximation algorithm for MAX2SAT and MAXCUT. In Proc. 26th ACM Symp. on Theory of Computing, pages 422431, 1994.]