| 作成者 |
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
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.続きを見る
|
Mendeley出力
