Efficient approximation algorithms for the Hamming center problem

The Hamming center problem for a set S of k binary strings, each of length n, is to find a binary string β of length n that minimizes the maximum Hamming distance between β and any string in S. Its decision version is known to be NP-complete. We provide several approximation algorithms for the Hamming center problem. Our main result is a randomized (4/3+ε) approximation algorithm running in polynomial time if the Hamming radius of S is at least superlogarithmic in k. Furthermore, we show how to find in polynomial time a set B of O(log k) strings of length n such that for each string in S there is at least one string in B within Hamming distance not exceeding the radius of S.