The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it is at least as good as any other spanner construction in terms of both the size and weight parameters. However, a rigorous proof for this statement has remained elusive. In this work we fill in the theoretical gap via a surprisingly simple observation: The greedy spanner is existentially optimal (or existentially near-optimal) for several important graph families in terms of both size and weight. Roughly speaking, the greedy spanner is said to be existentially optimal (or near-optimal) for a graph family G if the worst performance of the greedy spanner over all graphs in G is just as good (or nearly as good) as the worst performance of an optimal spanner over all graphs in G. Focusing on the weight parameter, the state-of-the-art spanner constructions for both general graphs (due to Chechik and Wulff-Nilsen [ACM Trans. Algorithms, 14 (2018), 33]) and doubling metrics (due to Gottlieb [Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, 2015, pp. 759-772]) are complex. Plugging our observation into these results, we conclude that the greedy spanner achieves near-optimal weight guarantees for both general graphs and doubling metrics, thus resolving two longstanding conjectures in the area. Further, we observe that approximate-greedy spanners are existentially near-optimal as well. Consequently, we provide an O(n log n)-time construction of (1 + epsilon)-spanners for doubling metrics with constant lightness and degree. Our construction improves Gottlieb's construction, whose runtime is O(n log(2)n) and whose number of edges and degree are unbounded, and, remarkably, it matches the state-of-the-art Euclidean result (due to Gudmundsson, Levcopoulos, and Narasimhan [SIAM J. Comput., 31 (2002), pp. 1479-1500]) in all of the involved parameters (up to dependencies on epsilon and the dimension).
展开▼
