An Optimal Algorithm for Binary Closest String

Abstract

We revisit the Binary Closest String problem, which asks, given a set of binary strings $X\subseteq \{0,1{\}}^n$, to compute a string minimizing the maximum Hamming distance to $X$. A long line of work has focused on parameterized algorithms with respect to the optimal distance $d$, yielding a sequence of improvements from $O^{\ast }(d^d)$ through $O^{\ast }(16^d)$, $O^{\ast }(9.513^d)$, $O^{\ast }(8^d)$, $O^{\ast }(6.731^d)$ to the current best-known running time of $O^{\ast }(5^d)$ [Chen, Ma, Wang; Algorithmica '16]. We present a faster randomized algorithm running in time $O^{\ast }(4^d)$. Our result matches a recent fine-grained lower bound [Abboud, Fischer, Goldenberg, Karthik C.S., Safier; ESA '23], and is therefore conditionally optimal. As an extra benefit, our algorithm is remarkably simple.