グラフの一般化であるハイパーグラフ H = ( V , E )では, 辺は任 意個の頂点の部分集合で定められる. ハイパーグラフの頂点被覆を 求める問題は, " U の頂点によって, E の全ての辺が被覆される" 様なV の部分集合U を, U の各頂点に付いたコストの総和を最小化 する条件の下で求める問題である. この問題は, 頂点を集合, 辺を要素と見なすと, セットカバー問題 と同値である. ところでセットカバー問題は NP 困難であり, 直接 最適解を求めることは非常に難しい. そのため, 近似解を求めるこ とが必要となり, また有効な手段となる. 近似解を求める方法とし ては, 貪欲算法, ホッフバウムの解法, 等がある. ただし, 近似解 を求める際は近似限界が存在するので, それを許容せざるを得ない. この研究では, それぞれの近似解法における近似限界を調べるとと もに, その近似限界となるときのハイパーグラフの形状を求めるこ とが目的である. セットカバー問題は航空乗務員のスケジューリングや企業のリスト ラ計画など, 計画に効率性を求める問題に応用が効く. そのために 歴史的に様々な近似法が考案されたセットカバー問題をハイパーグ ラフとしてとらえることで, 抽象的なものを具体化して捕らえるこ とができる, ということがこの問題の背景にある.