@techreport{oai:ipsj.ixsq.nii.ac.jp:00033623,
 author = {竹下, 和彦 and 藤戸, 敏弘 and 渡邉, 敏正 and Kazuhiko, Takeshita and Toshihiro, Fujito and Toshimasa, Watanabe},
 issue = {15(1998-MPS-023)},
 month = {Feb},
 note = {ハイパーグラフは，頂点集合とその部分集合（ハイパー辺）族から構成される．ハイパーグラフ問題はグラフ問題の一般化であるが，ハイパーグラフ問題に対する近似解法に関する研究はグラフ問題ほど進んでいない．本稿では，The generalized Steiner tree problemをはじめとするいくつかのグラフ問題をハイパーグラフ上に一般化し，これらの問題の近似解法について考える．具体的には，Goemans，Williamson[2］がグラフ問題に対して提案した主双対法に基づく近似アルゴリズムをハイパーグラフ問題に適用できるように拡張し，その近似解のコストが最悪の場合でも最適解のコストのk倍以下であることを示す．ここで，kは入力ハイパーグラフ中のハイパー辺次数の最大値である．, 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.},
 title = {いくつかのハイパーグラフ問題に対する　Primal - Dual近似アルゴリズムについて},
 year = {1999}
}