Center and Distinguisher for Strings with Unbounded Alphabet |
| |
Authors: | Xiaotie Deng Guojun Li Lusheng Wang |
| |
Institution: | (1) Department of Computer Science, City University of Hong Kong, Hong Kong, People's Republic of China;(2) School of Mathematics and System Science, Shandong University, Jinan, 250100, People's Republic of China;(3) Department of Computer Science, City University of Hong Kong, Hong Kong, People's Republic of China |
| |
Abstract: | Consider two sets
and
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
is a string that minimizes the maximum of Hamming1
distance(s, s*) over all string s : s
. In contrast, a farthest string t* from
maximizes the minimum of Hamming distance(t*,t) over all elements t: t
. A distinguisher of
from
is a string that is close to every string in
and far away from any string in
. We obtain polynomial time approximation schemes to settle the above problems. |
| |
Keywords: | approximation algorithm computational molecular biology center string selection distinguishing string selection unbounded alphabet size |
本文献已被 SpringerLink 等数据库收录! |
|