<テクニカルレポート>
An Approximation Algorithm for Alphabet Indexing Problem

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 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 14  
96.ps.tar pdf 166 KB 24  

詳細

レコードID
査読有無
関連情報
主題
タイプ
登録日 2009.04.22
更新日 2017.01.20