著者

藤戸 敏弘 奥村 将

出版者

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

雑誌

電子情報通信学会技術研究報告. 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, という近似保証の得られることを、線形計画緩和とその双対を用いて示す。