Ulam Metric $k$-Center in Parameterized Linear Time

Continuous Ulam Metric $k$-Center asks for at most $k$ permutations whose radius-$d$ balls cover the input rankings. For $m$ rankings of $n$ symbols, a deterministic algorithm takes $2^{O(kd\log(k+d+2))}mn$ word operations. Permanent reference rankings, short insertion lists, and small obstructions obtained by patience sorting control the search. For one center, this answers a question of Bai, Fomin, Golovach, More, and Wietheger with linear input dependence. An arbitrary-alphabet Hamming embedding with a nonexpansive retraction also gives the matching $2^{o(d\log d)}$ exclusion under the Exponential Time Hypothesis.