Creator |
|
Language |
|
Publisher |
|
|
Date |
|
Source Title |
|
Vol |
|
Publication Type |
|
Access Rights |
|
Related DOI |
|
|
Related URI |
|
|
Relation |
|
|
Abstract |
Alphabet Indexing is the problem to find a mapping $f : sum \rightarrow { 1,...,K } $ for alphabet $sum$, positive integer $K$ and a pair of disjoint sets of strings $P,Q sbseteq sum^*$ such that $f$ ...transforms no two strings from $P$ and $Q$ into identical ones. Although Alphabet Indexing problem is NP-complete, we define a combinatorial optimization problem, Max K-Indexing, and propose a simple greedy algorithm for this problem. Then we show that the algorithm achieves the constant error ratio $1/K$ for $K-indexing$ with respect to the number of distinguishable pairs and our problem is MAX SNP-hard.show more
|