Motivation
Independent random signs cut each edge with probability one half. A better algorithm should use information about which pairs would benefit from separation, while retaining enough structure to turn that information into a genuine cut. Unit vectors provide an intermediate language: opposite directions express a strong desire to separate, identical directions express none, and intermediate angles encode partial separation.
A random hyperplane converts every vector into a sign using one common geometric choice. The resulting edge events are correlated, but their individual probabilities have a simple angle formula. Comparing that formula with the relaxation's objective is the heart of the approximation proof. Neither drawing vectors nor solving a continuous program alone gives a cut guarantee; the comparison closes that gap.
Definitions
Definition 11.1.1
(Weighted Max-Cut and its vector relaxation)
Let be a finite loopless undirected graph with vertices and nonnegative weights on its edges. A cut assigns signs and has weight
Let be its maximum. The vector relaxation assigns each vertex a unit vector and maximizes
Write for this maximum. Each edge is counted once, not once in each orientation.
A sign solution is a feasible vector solution by taking , so . This is an upper bound because the problem is a maximization. The unit-sphere constraint is not itself a convex description in the vector coordinates; the matrix formulation reveals the semidefinite structure.
Definition 11.1.2
(Positive semidefinite Gram matrices)
A real symmetric matrix is positive semidefinite, written , if for every real vector . A Gram matrix has entries . The relaxation is equivalently
Every Gram matrix is positive semidefinite, since its quadratic form is . Conversely, the real symmetric spectral theorem factors a positive semidefinite matrix as ; take the rows of as the vectors. Diagonal ones make those rows unit vectors. The spectral theorem is a linear-algebra prerequisite used here, not reproved. The feasible matrix set is convex: nonnegative weighted averages preserve its quadratic-form inequalities and diagonal constraints.
Theorems
Theorem 11.1.3
(Random-hyperplane crossing probability)
Draw with independent standard normal coordinates, and set when , and otherwise. For two unit vectors with angle ,
Thus the expected rounded cut value is .
Theorem 11.1.4
(An exact approximation constant)
Define
For every feasible vector solution, random-hyperplane rounding satisfies . For an optimal vector solution this gives . The minimum is attained at the unique satisfying .
The exact constant is the displayed minimum, approximately . The rigorous numerical lower bound is recorded in Goemans and Williamson, Lemma 3.5. The calculus characterization will be proved below; the decimal lower bound is a cited numerical refinement, not inferred from a floating-point calculation in these notes. Implementation of a polynomial-time semidefinite optimizer and certified numerical precision are outside this chapter.
Proof sketch or proof idea
Why the Gaussian gives a uniform angle
The joint standard-normal density is proportional to and is unchanged under orthogonal changes of coordinates. If , the two vectors span a plane. Projection of onto an orthonormal coordinate system in that plane has a rotationally symmetric two-dimensional normal distribution. In polar coordinates its density is a function of radius alone, so its angle is uniform on a full turn.
The projected normal gives different signs to the two vectors in two angular sectors, each of width . One can see this by rotating the normal: each vector's positive half-circle has length , and the symmetric difference of the two half-circles has total length . Dividing by gives . If , the vectors coincide and the signs always agree. If , they are opposite and the signs disagree except on a probability-zero perpendicular hyperplane. These cases also fit the formula.
Each unit vector has a nondegenerate normal inner product, so an exact zero has probability zero. The arbitrary sign convention at zero therefore does not change the probabilities. With finitely many vertices the probability that any such tie occurs is still zero. The argument uses a continuous ideal distribution; replacing it by finite-precision sampling needs separate error control.
Let indicate that an edge crosses. Since cut weight is , linearity of expectation proves the expected-value formula. Independence between the edge indicators is unnecessary and generally false: a single hyperplane determines every sign at once. This is a useful example where correlated rounding admits an exact analysis through marginal probabilities alone.
Concept lensAnalytic
Rounding as an entrywise arcsine of the Gram matrix
Encode the rounded signs as the random matrix . Since , the crossing probability gives
because . So rounding replaces the Gram matrix by the matrix with entries in expectation. For the triangle, becomes , matching the average of the products .
From angles to the objective
Proof
(Rounding loses at most the factor )
Fix a feasible vector solution and write for each edge. For an edge with , the definition of as a minimum, evaluated at , gives
At both sides are zero. Multiply each edge inequality by its weight , which preserves its direction, and sum over edges. By the crossing probability theorem and linearity of expectation,
For an optimal relaxation, , so .
Proof X-ray
Which step uses which hypothesis
The proof composes four steps, and each one spends a different hypothesis. First, the crossing probability is an equality, so the rounding loses nothing there. It needs only the Gaussian symmetry of the hyperplane and the marginal law of each pair, and it never needs independence between edges. Second, the displayed scalar inequality is the only lossy step and the only place where enters. It holds edge by edge, so it can be applied to every edge angle at once. It is tight only at the angle : at the ratio equals , so an edge whose vectors are opposite loses nothing.
Third, summation requires . Take one edge of weight with opposite vectors: then and , but , so the claimed inequality fails. Fourth, the passage to uses that is an optimal relaxation solution, so , together with from embedding sign solutions. Remove optimality and only survives.
The guarantee has two comparisons with different sources. Geometry compares expected rounding to the supplied vector value; relaxation compares its optimal vector value with the integral optimum. If arbitrary poor vectors are supplied, only the first comparison is justified. This distinction prevents feasibility from being confused with approximate optimality.
Locating the exact scalar minimum
Put . As , the expansion gives . Its derivative has the sign of
Starting from , this function strictly decreases on and strictly increases on . Also and . Continuity and strict monotonicity give exactly one zero in the latter interval. Thus decreases until that point and increases afterward, proving the minimum characterization.
The equation is . The half-angle identities and turn this into . It also yields . These exact identities, not a rounded decimal, define the guarantee proved here. As a weaker elementary check, on because the derivative of their difference is ; hence .
Approximate optimization and what is actually promised
The matrix feasible region is closed and bounded: positive semidefiniteness and diagonal ones imply , either from the Gram interpretation or the associated two-by-two quadratic form. It is nonempty, for example at the identity matrix. A continuous linear objective therefore attains a maximum. This existence argument does not give a finite exact algorithm for finding that maximum.
If a solver supplies a truly feasible vector solution with for , the same proof gives
This is an additive-error statement. To obtain a ratio loss of at most when , one needs , or an explicit usable lower bound on the optimum that implies it. Merely reporting a small numerical residual does not prove either feasibility or this objective condition. Near-positive-semidefinite matrices need a justified repair before the exact-vector theorem applies.
An expectation guarantee also does not apply to every random sample. If is a rounded cut value, . For and , let when the expected bound is . Bounding successful values by and all other values by the threshold gives
Independent repetitions and keeping the best observed cut reduce the failure probability to at most after rounds, where is the displayed lower bound. The algorithm need not know the optimum to retain its best output; the threshold is used only in the analysis. If all weights are zero, every cut is optimal and this division-based discussion is unnecessary.
Proof X-ray
Where the approximation ratio comes from
The proof has three bridges: an integral sign assignment is a feasible Gram matrix; an edge angle determines its hyperplane-separation probability; and one scalar inequality compares that probability with the edge's relaxed contribution. Summing the last comparison requires nonnegative weights. Keeping these bridges separate shows which conclusion fails when vectors are not optimized, when rounding is changed, or when weights can be negative.
Worked examples
Worked example 11.1.5
(One edge with opposite vectors)
For one edge of weight , take . The angle is , its relaxed contribution is , and every nonperpendicular hyperplane separates the pair. The rounded cut therefore has weight with probability one. The factor is one on this instance, exceeding the worst-case constant; a universal lower bound need not be tight on each input.
Worked example 11.1.6
(A triangle separates relaxation value from cut value)
For an unweighted triangle, put three planar unit vectors at angles zero, , and . Every pair has inner product , so . Every edge crosses with probability , giving expected cut value two, which is the integral optimum. The edge events are correlated: apart from probability-zero boundary cases, exactly two edges cross. A fractional objective of does not assert a cut of that impossible value.
Worked example 11.1.7
(Weighted expectations add without independence)
Take the two-edge path , with weights two and three. Let , , and . The edge angles are and , so expected cut weight is . The vector objective is . The integral optimum is five, achieved by separating vertex two from both endpoints. These feasible vectors are not optimal, so the theorem compares to , not automatically to .
Counterexample mode
Feasible vectors alone do not approximate the optimum
False claim: every feasible vector solution, rounded by a random hyperplane, yields a cut of expected weight at least . Take one edge of weight and assign identical unit vectors . The Gram matrix is positive semidefinite with unit diagonal, so it is feasible. The angle is , hence and the pair is never separated: the rounded cut has weight . But and . The theorem is not contradicted, since it only promises . The repair is to supply an optimal or provably near-optimal relaxation solution: with the vector objective is and the rounded cut has weight with probability one. Rounding quality and optimization quality are separate requirements.
Common mistakes
Common mistake
(PSD does not mean entrywise nonnegative, and edge events are not independent)
Positive semidefinite does not mean every entry is nonnegative; the triangle uses negative off-diagonal entries. Nor is a vector objective itself a feasible discrete cut. The hyperplane is shared across vertices, so one cannot multiply edge probabilities as though all crossing events were independent.
Common mistake
(A decimal is not the theorem constant)
A decimal approximation to is not an exact theorem constant. The exact minimum, an explicitly proved lower bound, and solver tolerance have different roles. Numerical optimization and sampling can approximate the ideal algorithm, but their errors must be connected to a stated additive or multiplicative guarantee rather than hidden in implementation language.
Summary
Gram matrices convexify sign products while retaining every actual cut. Rotational symmetry gives an exact angle crossing probability, and a one-variable comparison yields the expected approximation factor. The scalar minimum and its unique stationary angle are characterized rigorously; optimized vectors, nonnegative weights, and controlled numerical error remain explicit requirements.
Exercises
Quick check
(Show directly that a Gram matrix is positive semidefinite, and explain why unit vectors force diagonal entries one.)
Solution · Answer
For any real coefficients , . Also . This proves the two required constraints without assuming that individual entries are positive.
Quick check
(For two orthogonal unit vectors, compute their relaxed edge contribution and their crossing probability for an edge of weight four.)
Solution · Answer
The angle is and the inner product is zero. The relaxed contribution is , while crossing probability is and expected cut contribution is also two. The probability and the weighted contribution have different units and should not be identified.
Quick check
(Prove that the triangle's vector optimum is exactly , rather than only showing a feasible value.)
Solution · Answer
For any three unit vectors, . Thus the sum of pair inner products is at least , and the triangle objective is at most . The displayed equally spaced vectors attain that value. The integral optimum is two, so this also proves the exact relaxation gap for the triangle.
Quick check
(Under an exact expected guarantee and positive optimum, take . State a positive lower bound on the probability of achieving at least times optimum, and the failure bound after independent repetitions.)
Solution · Answer
The general bound gives . Taking the best of independent hyperplanes has failure probability at most . Independence is required between repetitions for this product bound, even though independence between edges within one rounding is not required for the expectation proof.