TY - JOUR
T1 - Center and distinguisher for strings with unbounded alphabet
AU - Deng, Xiaotie
AU - Li, Guojun
AU - Wang, Lusheng
PY - 2002/12
Y1 - 2002/12
N2 - Consider two sets B and G of strings of length L with characters from an unbounded alphabet Σ, i.e., the size of Σ is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of B is a string that minimizes the maximum of Hamming1 distance(s, s*) over all string s : s ∈ B. In contrast, a farthest string t* from G maximizes the minimum of Hamming distance(t*, t) over all elements t : t ∈ G. A distinguisher of B from G is a string that is close to every string in B and far away from any string in G. We obtain polynomial time approximation schemes to settle the above problems.
AB - Consider two sets B and G of strings of length L with characters from an unbounded alphabet Σ, i.e., the size of Σ is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of B is a string that minimizes the maximum of Hamming1 distance(s, s*) over all string s : s ∈ B. In contrast, a farthest string t* from G maximizes the minimum of Hamming distance(t*, t) over all elements t : t ∈ G. A distinguisher of B from G is a string that is close to every string in B and far away from any string in G. We obtain polynomial time approximation schemes to settle the above problems.
KW - Approximation algorithm
KW - Center string selection
KW - Computational molecular biology
KW - Distinguishing string selection
KW - Unbounded alphabet size
UR - http://www.scopus.com/inward/record.url?scp=0036887340&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0036887340&origin=recordpage
U2 - 10.1023/A:1019545003953
DO - 10.1023/A:1019545003953
M3 - 21_Publication in refereed journal
VL - 6
SP - 383
EP - 400
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 4
ER -