Center and distinguisher for strings with unbounded alphabet

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)383-400
Journal / PublicationJournal of Combinatorial Optimization
Volume6
Issue number4
Publication statusPublished - Dec 2002

Abstract

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.

Research Area(s)

  • Approximation algorithm, Center string selection, Computational molecular biology, Distinguishing string selection, Unbounded alphabet size