WEKO3
アイテム
最小キーおよび最適部分構造スクリーンの近似
https://ipsj.ixsq.nii.ac.jp/records/32329
https://ipsj.ixsq.nii.ac.jp/records/32329bcc00fa9-a756-4104-ab03-db235895fccf
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1995 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1995-09-21 | |||||||
タイトル | ||||||||
タイトル | 最小キーおよび最適部分構造スクリーンの近似 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Approximating Minimum Keys and Optimal Substructure Screens | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
群馬大学工学部情報工学科 | ||||||||
著者所属 | ||||||||
群馬大学工学部情報工学科 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Computer Science, Gunma University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Computer Science, Gunma University | ||||||||
著者名 |
阿久津, 達也
× 阿久津, 達也
|
|||||||
著者名(英) |
Tatsuya, Akutsu
× Tatsuya, Akutsu
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 化学構造データベースでは検索の効率化のために部分構造スクリーンが用いられるが、本稿ではスクリーンとして使用される最適な部分構造を選択する問題について考察する。この問題は関係データベース理論における最小キー問題と密接に関連しているが、両者ともにNP困難であるので、多項式時間近似アルゴリズムの観点から議論を行う。本稿では、両者ともに近似度はSET COVER問題と同等(Θ(og ))であること、Kolmogorov計算量を応用することにより部分構造スクリーン問題が平均的には定数以内の近似が可能であること、などを示す。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | In this paper, we consider the problem of selecting an optimal substructure screen, which is important in database systems for chemistry. This problem is closely related to the minimum cardinality key problem. Since both problems are NP-hard, we consider polynomial time approximation algorithms. We show that the performance ratios of both problems are Θ(log n) using reductions from/to the SET COVER problem. On the other hand, using Kolmogorov complexity, we show that the optimal substructure screen problem can be approximated within a factor of 2+〓 in the average case. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1995, 号 94(1995-AL-047), p. 17-24, 発行日 1995-09-21 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |