Efficient approximation algorithms for the Hamming center problem
Leszek Antoni Gąsieniec, Jesper Jansson, Andrzej Lingas · 1999
The Hamming center problem for a set S of k binary strings, each of length n, asks for a binary string of length n that minimizes the maximum Hamming distance between and any string in S. The decision version of this problem is known to be NP-complete [6]. 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 nd 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. 1 Introduction Let Z n 2 be the set of all strings of length n over the alphabet f0; 1g. For any 2 Z n 2 we use the notation [i] to refer to the symbol placed at the ith position of , where i = 1; ::; n, and we let [i::j] represent the substring of starting at position i and endin...