いくつかのハイパーグラフ問題に対する Primal - Dual近似アルゴリズムについて

• Item type: SIG Technical Reports(1)
• 公開日: 1999-02-18
• タイトル: いくつかのハイパーグラフ問題に対する Primal - Dual近似アルゴリズムについて
• タイトル / 言語: en
• タイトル: On Primal - Dual Approximation Algorithms for Several Hypergraph Problems
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属: 広島大学工学部第二類回路・システム工学講座
• 著者所属: 広島大学工学部第二類回路・システム工学講座
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者名: 竹下, 和彦; 藤戸, 敏弘; 渡邉, 敏正
• 著者名(英): Kazuhiko, Takeshita; Toshihiro, Fujito; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ハイパーグラフは，頂点集合とその部分集合（ハイパー辺）族から構成される．ハイパーグラフ問題はグラフ問題の一般化であるが，ハイパーグラフ問題に対する近似解法に関する研究はグラフ問題ほど進んでいない．本稿では，The generalized Steiner tree problemをはじめとするいくつかのグラフ問題をハイパーグラフ上に一般化し，これらの問題の近似解法について考える．具体的には，Goemans，Williamson[2］がグラフ問題に対して提案した主双対法に基づく近似アルゴリズムをハイパーグラフ問題に適用できるように拡張し，その近似解のコストが最悪の場合でも最適解のコストのk倍以下であることを示す．ここで，kは入力ハイパーグラフ中のハイパー辺次数の最大値である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A hypergraph consists of a vertex set and a family of its subsets. Although hypergraph problems are a generalization of graph problems, it seems that research results on approximation algorithms for hypergraph problems are much less than those for graph problems. In this paper, we propose approximation algorithms for several hypergraph problems including the generalized Steiner tree problem for hypergraphs : the primal-dual approximation algorithm provided by Goemans and Williamson[2] is adapted for solving these hypergraph problems. The main result is that the proposed algorithm outputs an approximation solution of cost at most k times the optimal, where k is the maximum size of hyperedges in a given hypergraph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 1999, 号 15(1998-MPS-023), p. 19-24, 発行日 1999-02-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会