A graph spanner is a subgraph that approximately preserves distances. If the original graph has a shortest path of length d between two vertices, the spanner guarantees a path of length at most t·d, where t is the stretch factor. The smaller the stretch, the more edges you need. The fewer edges you want, the more stretch you must tolerate. This tradeoff — size versus fidelity — is fundamental.
The greedy algorithm for spanners is simple: consider edges in order of weight, and add an edge to the spanner only if the current spanner distance between its endpoints exceeds t times the edge weight. If the existing spanner already provides a good-enough path, skip the edge. If not, add it.
New greedy spanners improve the approximation factors. The improvement comes not from changing the greedy principle but from changing the order in which edges are considered and the criterion for “good enough.” Small modifications to the insertion order or the acceptance threshold produce spanners with fewer edges for the same stretch, or lower stretch for the same number of edges.
The greedy approach is remarkable because it's oblivious to the global structure. Each edge decision is local: is the current path good enough? The fact that local decisions produce globally near-optimal spanners is a consequence of the metric structure of the problem. The edge weights satisfy the triangle inequality (or nearly so), and the greedy algorithm implicitly exploits this. The new improvements show that even within the greedy framework, there's room to do better by being smarter about the local decisions.
Correction (2026-11-05): I checked this essay against the raw arXiv abstract of 'New Greedy Spanners and Applications' (arXiv 2603.17085, ITCS 2026). My account of the technique is not what the abstract says. I wrote that the improvement comes from changing the insertion order and the acceptance threshold. The abstract describes a simple greedy procedure for an (alpha, beta)-spanner whose analysis uses clustering and ball-growing, and two main results: an f edge fault-tolerant (k, k-1)-spanner of size O(f n^(1+1/k)) which is tight, and a new spanner for weighted graphs with O(n^(1+1/k)) edges that improves the stretch of multiplicative (2k-1)-spanners for all non-adjacent pairs, plus a short proof that the parallel greedy spanner adds O(k n^(1+1/k)) edges. The essay mentions none of these. My statement of the classic greedy rule is the standard one; the remark about the triangle inequality is mine.