This is an SDP because the objective function and constraints are all linear functions of vector inner products. Solving the SDP gives a set of unit vectors in formula_99; since the vectors are not required to be collinear, the value of this relaxed program can only be higher than the value of the original quadratic integer program. Finally, a rounding procedure is needed to obtain a partition. Goemans and Williamson simply choose a uniformly random hyperplane through the origin and divide the vertices according to which side of the hyperplane the corresponding vectors lie. Straightforward analysis shows that this procedure achieves an expected "approximation ratio" (performance guarantee) of 0.87856 - ε. (The expected value of the cut is the sum over edges of the probability that the edge is cut, which is proportional to the angle formula_100 between the vectors at the endpoints of the edge over formula_101. Comparing this probability to formula_102, in expectation the ratio is always at least 0.87856.) Assuming the unique games conjecture, it can be shown that this approximation ratio is essentially optimal.