| 講演名 | 2002/5/17 2値重み集合被覆問題に対する貪欲法の改良について 奥村 将, 藤戸 敏弘, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 集合被覆問題とは,資源選択問題などをモデル化した問題であり,NP完全な問題であることが知られている.この問題は要素の集合UとUの重みつき部分集合の族が与えられたとき,Uのすべての要素を被覆する重みの合計が最小の部分集合族を求める問題でる.特に,部分集合の最大サイズがκである集合被覆問題はκ集合被覆問題と呼ばれ,貪欲法によりE(κ)Σ^κ_i=1(1/i)の近似保証が得られることが知られている。又,任意の重み付きの場合については,これよりも良い近似保証のものは知られていない.そこで,本稿では重みが2種類の場合の3-集合被覆問題を対象とする.重みが1と2以上の場合については近似保証がH(3)-1/6となることが以前に示されている。従って,本稿では重みが1と1.5以上3以下の定数の2種類の場合について考え,この場合についても貪欲法を改良することにより,同様にH(3)-1/6の近似保証が得られるということを線形計画法とその双対を用いて示す. |
| 抄録(英) | The set cover problem is an optimization problem that models many resource selection problems. Given a base set U and a family of weighted subsets of U , the problem is to find a minimum weight subfamily such that each element of U belongs to at least one subset in the subfamily. The k-set cover problem is its variant where each subset is of size at most κ. The greedy algorithm is known to yield a performance ratio of H(κ)=∑^κ_i=1(1/i) , but no better bound is shown except for the case of unweight subsets. In this paper we consider the 3-set cover problem where subset weights are restricted to 1 and some constant d. For the case of d≧2 the approximation bound of H(3) - 1/6 was previously obtained. So we consider the case of 1.5≦d≦3 and show how to modify the greedy algorithm, using the LP duality, so as to yield the same approximation bound. |
| キーワード(和) | 集合被覆問題 / 近似アルゴリズム / 貪欲法 |
| キーワード(英) | set cover / approximation algorithm / greedy algorithm |
| 資料番号 | COMP 2002-14 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2002/5/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2値重み集合被覆問題に対する貪欲法の改良について |
| サブタイトル（和） | |
| タイトル（英） | A Modified Greedy Algorithm for Set Cover Problem with 2 Weights |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 集合被覆問題 / set cover |
| キーワード(2)（和/英） | 近似アルゴリズム / approximation algorithm |
| キーワード(3)（和/英） | 貪欲法 / greedy algorithm |
| 第 1 著者 氏名（和/英） | 奥村 将 / Tsuyoshi OKUMURA |
| 第 1 著者 所属（和/英） | 名古屋大学工学研究科電子工学専攻 Department of Electronics, Nagoya University |
| 第 2 著者 氏名（和/英） | 藤戸 敏弘 / Toshihiro FUJITO |
| 第 2 著者 所属（和/英） | 名古屋大学工学研究科電子工学専攻 Department of Electronics, Nagoya University |
| 発表年月日 | 2002/5/17 |
| 資料番号 | COMP 2002-14 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 90 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |