著者

藤戸 敏弘 奥村 将

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.184, pp.17-24, 2001-07-09

---

集合被覆問題とは、集合Uの(コストつき)部分集合の族が与えられ、Uの任意の要素が、その部分集合により被覆される(含まれる)ような、最小コストの部分族を計算する最適化問題である。又、与えられる部分集合の大きさがある定数κ以下の場合には、κ集合被覆問題と呼ばれる。同問題に対しては、近似保証がH(κ)=Σ^κ_<i=1>(1/i)の解が貪欲法により求まることが、よく知られているが、部分集合コストが一定である場合を除き、より良い近似保証は知られていない。そこでまず手始めとして、部分集合コストが1ないし2に限定されたκ集合被覆問題を、本稿では対象とする。貪欲法を適切に改良することで、3-集合被覆問題に対してはH(3)-1/6, κ-集合被覆問題に対してはH(κ)-1/12, という近似保証の得られることを、線形計画緩和とその双対を用いて示す。

著者

藤戸 敏弘 藤原 洋志

出版者

豊橋技術科学大学

雑誌

基盤研究(C)

巻号頁・発行日

2011-04-28

---

1.最小コスト木被覆問題・有向シュタイナー木問題・有向木被覆問題・b辺支配集合問題などのNP困難なグラフやネットワーク上での組合せ最適化問題に対し,新たに近似アルゴリズムを設計し,従来からの近似保証を改善した.2.侵入者と守衛の間で行われるグラフ護衛ゲームにおいて,最小の守衛数を求める問題に対し,従来手法を拡張し,侵入者が木上を移動する場合でもΘ(log n)倍以下で近似可能であることを示した.3.多状態スキーレンタル問題について,いかなるインスタンスに対し最適戦略をとっても,競合比はe/(e-1)より小さくできないことを示した.