Ward's method on the line can cost 3.69 times the optimum

Editorial revision; no result changed. Corrections in v1.3: The Zenodo description now carries the paper's current abstract (the v1.2 record still showed the longer v1.1 abstract). The abstract is shortened to 179 words. The paper now states where the supplementary material is (this record; concept DOI 10.5281/zenodo.24011093), and SHA256SUMS.txt is uploaded with the release files. New Figure 2: one backward step (Lemma 4.1), the split of a cluster and the three comparisons that make it consistent with a Ward run. Figure 4 (definitions for general k): label collisions removed. Corrections: the searches maximise the ratio only for k ≤ 5 (other quantities also at k = 6, Remark F.20), previously 'k ≤ 5' without qualification; the best value 3.694914253 is attributed to the beam-search spine of Section 4.2 (the hill-climbing searches of Appendix C reach 3.694899); the certified instance uses the beam-search side pattern alone, without the alternating tail; the 'one step made explicit' now points to Lemma F.14; the failed certification of 4.68 is described as a check (4.68 is below the maximum of F). Wording: the warm-up is no longer titled 'by hand', and the bound 5 is labelled 'short proof, no computer'; a parenthetical about who wrote the two exact checking programs was removed; a repeated limitation and a repeated practical paragraph were removed; long sentences split. Supplement: README title now matches the paper; the paper's LaTeX sources under paper/ are the current ones; the search logs folder is renamed results/search_logs/ (scripts updated); internal SHA256SUMS added; empty files are not shipped. Scripts and results otherwise unchanged; rerun_all.sh regenerates every generated LaTeX input byte-identically. No theorem, lemma or proof changed (all 99 environments identical apart from the removed parenthetical in the proof of Theorem 4.2). Theorem and table numbers are unchanged; figures after Figure 1 are renumbered. Abstract. Ward's method, the default linkage of scikit-learn, clusters data by repeatedly merging the two clusters whose union increases the k-means cost the least. How much more than the optimal k-means cost can its k-clustering cost? On the line, Großwendt, Röglin and Schmidt (SODA 2019) proved that the ratio is bounded by a constant they did not compute, and Großwendt's thesis conjectures that the worst ratio is 2+√2 ≈ 3.414, approached by an instance of Schrenk. We refute this conjecture with a 28-point weighted instance, with two very heavy end points, on which Ward's 2-clustering costs 3.6949 times the optimum, verified in exact rational arithmetic. The key idea is to run Ward's method backwards: a run is a sequence of splits, each allowed exactly when three inequalities hold, and our instance grows Schrenk's instance by repeatedly splitting off one point at a three-way tie. In the other direction, making their analysis explicit, we show that Ward's k-clustering on the line costs at most 89.18 times the optimum for every k, and at most 4.70 times for k = 2. Supplementary material (scripts, results, search logs, C search programs, README, MIT license) is in this record; all versions: concept DOI 10.5281/zenodo.24011093.