Minimum Multiset Covering 問題の近似アルゴリズムについて

スポンサーリンク

概要

• 論文の詳細を見る

• Minimum Multiset Coveringとは, 入力として有限集合U上の多重集合A^^とC(*⫅)2^Uが与えられたとき, できる限り小さなA^^の被覆C'(*⫅)Cを見つける問題である.この問題は, 最小集合被覆問題の自然な拡張となっている.本論文では, まずMinimum Multiset Coveringと特徴遺伝子集合の抽出問題関連について述べ, この問題の多項式時間近似アルゴリズムを示し, それが多重集合の総要素数がnの入力について近似率1+ln n を保証するアルゴリズムであることを証明する.さらに, 被覆に用いるCの要素を多重に拡張した問題に対しても, 同様の, 結果が得られることを示す.

• 社団法人電子情報通信学会の論文
• 2001-11-09

著者

• 阿久津 達也

  京都大学 化学研究所 バイオインフォマティクスセンター

• 下薗 真一

  九州工業大学 情報工学部

• 下薗 真一

  九州工業大学知能情報工学科

• 下薗 真一

  九州工業大学

• 柳浦 豊

  九州工業大学大学院 情報工学研究科 情報科学専攻

関連論文

• 木の編集距離の文字列の編集距離による近似
• 特徴ベクトルからの化学構造の推定(Bioinformatics)
• BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム
• 期待精度最大化に基づくRNAシュードノット予測
• 構造トポロジーと複雑ネットワーク特徴量からのタンパク質フォールディング速度予測
• 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
• グラフの極大成分を用いた生物ネットワークの解析(遺伝子発現・ネットワーク)
• タンパク質ドメインネットワークにおける混合スケールフリー次数分布(Protein domain network analysis)
• 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム(セッション5)
• 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム(セッション5)
• 文字列パターン照合のための損失のあるデータ圧縮
• BONSAI : 決定木とインデックス化による文字列からの機械発見システム
• 整数計画と帰還点集合による代謝ネットワークの構造的堅牢性の測定
• 生育温度による代謝ネットワーク構造の差異
• Complexity of Finding Alphabet Indexing(Fundamental Studies on Computational Complexity)
• 表面実相ロボットの実相シーケンスの決定に対する巡回セールスマン問題のアルゴリズムの適用
• 楽譜検索のための幾何点列の近似パタン照合(文字列アルゴリズム)
• テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
• 生物配列の局所マルチプルアラインメントの計算困難性
• 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
• Efficient Discovery of Maximal Two-Dimensional Patterns with Don't-Cares(extended abstract) (テーマ:特集「ウェブデータの知的処理」および一般)
• K語近接相関パタンの高速発見アルゴリズム
• On Approximation Algorithms for Local Multiple Alignment (合同研究会"AIシンポジウム'99"(第10回))
• 文字列相関パタンの分類精度最大化問題について
• 省スペースな線形時間文法圧縮アルゴリズム
• DS-1-9 二次元点集合近似照合によるグラフの格子状配置アルゴリズム(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
• Minimum Multiset Covering 問題の近似アルゴリズムについて
• 平面巡回セールスマン問題の高速な近似アルゴリズム
• 無矛盾最小OBDD問題の近似困難性について
• 遺伝子ネットワークの離散モデルと制御

もっと見る 閉じる

スポンサーリンク