Greedy MMR is a constant-factor approximation for relevance plus spanning-tree diversity

Editorial revision; no result changed. Corrections in v1.3: Credit to Halldórsson, Iwano, Katoh and Tokuyama (SIAM J. Discrete Math. 1999), checked against the article: their farthest-point algorithm starts from an arbitrary point, their Theorem 2.2 (with the bound 4 - 2/k in its proof) bounds every anticover, and their Theorem 2.3 instances (k = t^2) work for every starting point. The introduction, Section 5, Conjecture 9 and Remark 10 now state exactly this, and Conjecture 9 now gives (4k-8)/(k-1) ≤ rho_k^(0) ≤ 4 - 2/k, with a short explanation of why the bound applies with an adversarial first pick and tie-breaking. Proof of Proposition 12: the case of optimal items picked by MMR after step i-1 is now spelled out (it follows from the covering property and nonnegative relevance). Limitations: the additive cost of the relevance shift is stated exactly (5k-6, previously 'at least 2k'), and the bound 3k-2 on the unshifted objective is stated for the metric sqrt(2(1-sim)); the scope of the numerical evidence is stated correctly (local search for k ≤ 7, the two families for k ≤ 8, probes at k = 6, 9, 12, random checks for k ≤ 6). New 'Connections' paragraph (farthest-point selection and remote-MST, Borodin et al.'s sum-of-distances greedy, the companion note on greedy volume maximization). Abstract shortened to 180 words, with the weaker constants stated qualitatively; 'What is new' shortened; repeated caveats removed; long sentences split. The verification paragraph now names each script, says the checks are floating point, and says that re-running them is a re-run of the same programs, not a separately written re-check; it gives the Zenodo concept DOI of the supplement. Symbol clashes removed in the proofs of Lemma 4 and Proposition 7 (renamed indices and the angle). Two bibliography entries (LangChain, LlamaIndex) had relative links; they now link to the source files. Theorem numbering is unchanged. The supplement's scripts and results are unchanged; only its README version line differs. Abstract. Maximal marginal relevance (MMR) starts from the most relevant item and repeatedly adds the item with the largest relevance plus distance to its nearest chosen item; it is the built-in diversity option of the LangChain and LlamaIndex retrievers. A natural objective behind this rule is total relevance plus the weight of a minimum spanning tree on the k chosen items. With arbitrary nonnegative relevance, the best guarantee for MMR on this objective that we know of was O(log k) (Dasgupta et al., 2013). We show that MMR with a metric distance and nonnegative relevance is a constant-factor approximation: its ratio is at most 6 for every k, and about 5.8 for large k. The key idea is to hang each item's relevance on it as a 'dangling' edge, which turns MMR into farthest-point selection. The ratio can approach 4, and we conjecture that 4 is tight. The guarantee does not extend to the non-metric cosine distance 1 - cos of deployed retrievers: measured in 1 - cos, MMR's ratio can approach k - 1 (for k = 2^m + 1). Supplementary material (scripts, results, README, MIT license) is in this record; all versions: concept DOI 10.5281/zenodo.24009527.