Center and Distinguisher for Strings with Unbounded Alphabet

Xiaotie Deng, Guojun Li and Lusheng Wang
Additional contact information
Xiaotie Deng: City University of Hong Kong
Guojun Li: Shandong University
Lusheng Wang: City University of Hong Kong

Journal of Combinatorial Optimization, 2002, vol. 6, issue 4, No 2, 383-400

Abstract: Abstract Consider two sets $$\mathcal{B}$$ and $$\mathcal{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 $$\mathcal{B}$$ is a string that minimizes the maximum of Hamming1 distance(s, s*) over all string s : s ∈ $$\mathcal{B}$$ . In contrast, a farthest string t* from $$\mathcal{G}$$ maximizes the minimum of Hamming distance(t*,t) over all elements t: t ∈ $$\mathcal{G}$$ . A distinguisher of $$\mathcal{B}$$ from $$\mathcal{G}$$ is a string that is close to every string in $$\mathcal{B}$$ and far away from any string in $$\mathcal{G}$$ . 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 (search for similar items in EconPapers)
Date: 2002
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1019545003953 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:6:y:2002:i:4:d:10.1023_a:1019545003953

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1019545003953

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().