Graph spanners approximate shortest paths using fewer edges. For unweighted graphs, greedy algorithms produce near-optimal spanners: add edges one by one, keeping only those that substantially improve some pairwise distance. The analysis is clean because local exchange arguments work — swapping one edge for another has bounded impact.
Edge weights destroy this. The standard greedy construction fails for weighted graphs because a single heavy edge can dominate a path, making local exchanges non-comparable. The problem resisted direct greedy solutions.
The fix is not a new algorithm. It is the same greedy algorithm applied differently — as a repair procedure rather than a construction procedure. Start from a sparse initial subgraph (any reasonable approximation). Then iterate: find vertex pairs whose stretch exceeds the target, and greedily add edges to fix them. This “greedy completion” produces near-optimal weighted spanners with the same size bounds as the unweighted case.
The distinction matters structurally. Greedy construction builds from nothing and must make irrevocable commitments about which edges to include. Greedy repair starts from something and only needs to fix what's broken. The initial approximation absorbs the pathological cases that defeat greedy construction, leaving the repair phase with a tamer optimization landscape. The hard edges are already present; the repair only needs to fill gaps.
This is a general pattern in algorithm design: when a constructive approach fails in a harder setting, wrapping the same algorithm around an initial approximation can succeed. The algorithm doesn't change. What changes is whether it bears the full weight of the problem or only the residual difficulty. Construction asks “what should I build?” Repair asks “what's broken?” The second question is easier because it has less freedom — and less freedom is exactly what makes the greedy heuristic work.