The Unforeseen Power of Randomised Algorithms — Epoche C1
The claim, and why its usual examples do not establish it A randomised algorithm is one that is permitted to flip coins during its execution, so that its output or running time on a fixed input is a random variable rather than a fixed value. The common view is that this is a concession — that a deterministic algorithm, which behaves identically on every run, is the more rigorous object, and that randomness is what one settles for. The view is wrong, but it is wrong for narrower and more interesting reasons than are usually given, and two of the standard illustrations do not in fact establish anything. The corrections come out of the analysis below and are worth stating in advance, because the compressed version of this argument asserted both errors. First, the random algorithm for Maximum Cut that guarantees half the edges is matched exactly by a deterministic algorithm obtained from it mechanically, so it exhibits no advantage. Second, the approximation ratio of $0.878$ for Maximum Cut is not 'unattainable by deterministic methods unless P = NP'. The barrier there is NP-hardness, which applies to randomised and deterministic algorithms alike, and the algorithm achieving $0.878$ can itself be derandomised. What randomness genuinely and provably buys turns out to lie elsewhere. The random cut, and the deterministic algorithm hidden inside it Begin with the example that is easiest to check. The Maximum Cut problem takes an undirected graph $G = (V, E)$ and asks for a partition of the vertices into two sets maximising the number of edges with one endpoint in each set; such edges are said to be cut . The problem is NP-hard, meaning that a polynomial-time exact algorithm for it would give one for every problem in NP. The randomised algorithm assigns each vertex independently to one of the two sides with probability $1/2$ each. Fix an edge $\{u,v\}$. Its two endpoints receive one of four equally likely assignments, and exactly two of these — $u$ left with $v$ right, and $u$ right with $v$ left — place the endpoints on opposite sides. So each edge is cut with probability $1/2$. Let $X$ be the number of cut edges and $X_e$ the indicator that edge $e$ is cut. Linearity of expectation holds whether or not the $X_e$ are independent, which matters here because they are not; hence $$E[X] = \sum_{e \in E} E[X_e] = \sum_{e\in E} \tfrac{1}{2} = \frac{|E|}{2}.$$ Since the maximum cut is at most $|E|$, this is a $1/2$-approximation in expectation. It also yields a non-algorithmic fact by the probabilistic method: a random variable cannot always fall below its own mean, so some assignment cuts at least $|E|/2$ edges, and this is true of every graph. Now the turn the compressed version missed. That guarantee is achievable deterministically, by the method of conditional expectations, and the deterministic algorithm is read directly off the randomised one. Process the vertices in any fixed order. Having placed $v_1,\dots,v_{i-1}$, consider the conditional expectation of $X$ given those placements. Because $v_i$ is placed on each side with probability $1/2$, that conditional expectation is the average of the two conditional expectations obtained by placing $v_i$ left and right, so at least one of the two is not smaller. Place $v_i$ accordingly. The invariant 'conditional expectation of $X$ is at least $|E|/2$' therefore holds throughout, and once every vertex is placed the conditional expectation is the actual number of cut edges. Each step requires only counting $v_i$'s edges to already-placed vertices, so the whole procedure runs in linear time and always cuts at least $|E|/2$ edges. Randomness supplied the analysis; it supplied no power. Goemans–Williamson rounding, and what the $0.878$ barrier actually is The more sophisticated algorithm is genuinely stronger, and its constant deserves to be derived rather than quoted. Goemans and Williamson (1995) relax the problem. Instead of assigning each vertex $i$ a label $x_i \in \{-1,+1\}$ and maximising $\sum_{\{i,j\}\in E}\frac{1-x_ix_j}{2}$, they assign each vertex a unit vector $v_i$ in $\mathbb{R}^{|V|}$ and maximise $\sum_{\{i,j\}\in E}\frac{1 - \langle v_i, v_j\rangle}{2}$. Every $\pm 1$ labelling is a special case of a vector assignment, with all vectors parallel or antiparallel, so the relaxed optimum is at least the true optimum. The relaxation is a semidefinite program — an optimisation over positive semidefinite matrices, here the matrix of inner products $\langle v_i, v_j\rangle$ — and such programs are solvable to any fixed accuracy in polynomial time. Randomness enters in the rounding. Draw a hyperplane through the origin with uniformly random orientation, and put vertex $i$ on the side of the partition determined by which side of the hyperplane $v_i$ falls. Let $\theta_{ij}$ be the angle between $v_i$ and $v_j$. The probability that the hyperplane separates them can be computed exactly: project the hyperplane's normal onto the two-dimensional plane spanned by $v_i$ and $v_j$, where by symmetry the projected direction is uniform on the circle; the two vectors are separated precisely when that direction lies in one of two arcs of angular width $\theta_{ij}$, so the probability is $2\theta_{ij}/(2\pi) = \theta_{ij}/\pi$. Meanwhile the contribution of the edge to the relaxed objective is $(1-\cos\theta_{ij})/2$. The ratio of what the algorithm gains to what the relaxation counted is therefore $$\frac{\theta/\pi}{(1-\cos\theta)/2} = \frac{2\theta}{\pi\,(1-\cos\theta)},$$ and taking the worst case over $\theta$ in $(0,\pi]$ gives $\alpha \approx 0.87856$, attained near $\theta \approx 2.331$ radians. Since this holds edge by edge, linearity of expectation gives an expected cut of at least $\alpha$ times the relaxed optimum, which is at least $\alpha$ times the true optimum. Two things follow that the original statement of this result got wrong. The first is that determinism is not what the constant is protecting against: Håstad (2001) proved that it is NP