TY - GEN
T1 - Approximation algorithms for Hamming clustering problems
AU - Gąsieniec, Leszek
AU - Jansson, Jesper Andreas
AU - Lingas, Andrzej
PY - 2000/1/1
Y1 - 2000/1/1
N2 - We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by ϱ: The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S. First, we provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k and p are constant. We also observe that HDC admits straightforward polynomial- time solutions when k = O(log n) or p = 2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L1 metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any ε > 0 it is NP-hard to split S into at most pk1/7–ε clusters whose Hamming diameter doesn't exceed the p-diameter. Fur- thermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [6], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2O(pϱ/ε)kO(p/ε)n2-time (1+ε)-approximation algorithm for HRC. In particular, it runs in polynomial time when p = O(1) and ϱ = O(log(k+n)): Finally, we show how to find in O((formula presented) + kn log n + k2 log n)(2ϱk)2/ε) time a set L of O(p log k) strings of length n such that for each string in S there is at least one string in L within distance (1 + ε)%, for any constant 0 < ε < 1.
AB - We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by ϱ: The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S. First, we provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k and p are constant. We also observe that HDC admits straightforward polynomial- time solutions when k = O(log n) or p = 2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L1 metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any ε > 0 it is NP-hard to split S into at most pk1/7–ε clusters whose Hamming diameter doesn't exceed the p-diameter. Fur- thermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [6], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2O(pϱ/ε)kO(p/ε)n2-time (1+ε)-approximation algorithm for HRC. In particular, it runs in polynomial time when p = O(1) and ϱ = O(log(k+n)): Finally, we show how to find in O((formula presented) + kn log n + k2 log n)(2ϱk)2/ε) time a set L of O(p log k) strings of length n such that for each string in S there is at least one string in L within distance (1 + ε)%, for any constant 0 < ε < 1.
UR - http://www.scopus.com/inward/record.url?scp=84937395783&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 108
EP - 118
BT - Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings
PB - Springer Verlag
T2 - 11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000
Y2 - 21 June 2000 through 23 June 2000
ER -