## ＜テクニカルレポート＞An Approximation Algorithm for Alphabet Indexing Problem

作成者 作成者名 所属機関 所属機関名 Department of Control Engineering and Science, Kyushu Institute of Technology 九州工業大学情報工学部制御システム工学科 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1995-01 96 Accepted Manuscript open access RIFIS Technical Report || 96 http://www.i.kyushu-u.ac.jp/research/report.html 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.続きを見る

### 本文ファイル

96.ps tgz 53.8 KB 37
96.ps.tar pdf 166 KB 46

### 詳細

レコードID 3079 査読無 alphabet indexing approximation algorithm MAX-SNP combinatorial optimization テクニカルレポート 2009.04.22 2018.08.31