双対制限されたハイパーグラフ：部分横断と多重横断の列挙について

• Item type: SIG Technical Reports(1)
• 公開日: 2000-05-19
• タイトル: 双対制限されたハイパーグラフ：部分横断と多重横断の列挙について
• タイトル / 言語: en
• タイトル: Dual-Bounded Hypergraphs Generating Partial and Multiple Transversals
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: RUTCOR Rutgers University
• 著者所属: Russian Academy of Sciences
• 著者所属: Department of Computer Science Rutgers University
• 著者所属: 大阪大学大学院基礎工学研究科システム科学分野
• 著者所属(英): en
• 著者所属(英): RUTCOR, Rutgers University
• 著者所属(英): en
• 著者所属(英): Russian Academy of Sciences
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Rutgers University
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University
• 著者名: Boros, Endre; Gurvich, Vladimir; Khachiyan, Leonid; 牧野, 和久
• 著者名(英): Endre, Boros; Vladimir, Gurvich; Leonid, Khachiyan; Kazuhisa, Makino
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，データ発掘，学習理論の分野で現れる有限ハイパーグラフの横断の二つ自然な拡張，多重横断と部分横断について考える．我々は，すべての多重横断，あるいは，すべての部分横断から成るハイパーグラフが，その双対（横断）ハイパーグラフのサイズがそれ自身のサイズと入力ハイパーグラフのサイズの多項式で制限されるという意味で，双対制限されることを示す．我々の上界は，極値的集合理論，閾プール理論の新しい不等式に基づいている．我々は，与えられたハイパーグラフのすべての多重横断，あるいは，すべての部分横断を列挙する問題が，ハイパーグラフの横断を列挙する問題，すなわち，ハイパーグラフの有名な双対問題に多項式時間還元可能であることも示す．系として，ハイパーグラフのすべての多重横断，すべての部分横断，また，線形不等式で表される単調システムのすべての極小な0-1解の列挙が逐次擬多項式時間で可能なことも示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider two natural generalizations of the notion of transversal to a finite hypergraph, arising in data-mining and machine learning, the so called multiple and partial transversals. We show that the hypergraphs of all multiple and all partial transversals are dual- bounded in the sense that in both cases, the size of the dual hypergraph is bounded by a polynomial in the cardinality and the length of description of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals for a given hypergraph are polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known dualization problem for hypergraphs. As a corollary, we obtain incremental quasi-polynomial-time algorithms for both of the above problems, as well as for the generation of all the minimal Boolean solutions for an arbitrary monotone system of linear inequalities.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2000, 号 41(2000-AL-073), p. 35-42, 発行日 2000-05-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会