Christina Boucher

Given a set S of n strings, each of length l, and a non-negative value d, we define a center string as a string of length l that has Hamming distance at most d from each string in S. The Closest String problem aims to determine whether there exists a center string for a given set of strings S and input parameters n, l, and d. When n is relatively large with respect to l then the basic majority algorithm solves the Closest String problem efficiently, and the problem can also be solved efficiently when either n, l or d is reasonably small. Hence, the only case for which there is no known efficient algorithm is when n is between log l / log log l and log l. Using smoothed analysis, we prove that such Closest String instances can be solved efficiently by the O(nl + nd*d^d)-time algorithm by Gramm et al. In particular, we show that for any given Closest String instance I, the expected running time of this algorithm on a small perturbation of I is O((nl + nd *d^{2 + o(1))).

Christina Boucher. The Bounded Search Tree Algorithm for the Closest String Problem has Quadratic Smoothed Complexity. In proceedings of the 36th Annual Mathematical Foundations of Computer Science (MFCS 2011), pages 158--169.