| 講演名 | 2000/4/26 一般化されたオンライン独立頂点集合問題の競合化 武富 史郎, 宮崎 修一, 岩間 一雄, Halldorsson Magnus M., |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | オンライン独立頂点集合問題とは各時点で1つの頂点V_iと, V_iに接続する枝が与えられ, その頂点を独立頂点集合に入れるか否かを決定し, 最終的にできるだけ大きなサイズの独立頂点集合を得ることを目的とする問題である.従来の設定のように解を1つしか持つことを許さないモデルを用いた場合には, グラフの総頂点数をnとして, 競合比の上下限はn-1となる.本研究では同時に多項式個の解を保持することを許したモデルを2つ考案し, それぞれの競合比の上限と下限を与えた. |
| 抄録(英) | At each step of the online independent set problem, we are given a vertex and edges to the vertices previously given. We are reqired to decide whether we choose that vertex as a member of an independent set or not, before receiving the next vertex. In an ordinary setting of this problem, Halldorsson gave a tight upper and lower bound, n-1, of the competitive ratio. Also, he generalized the problem and gave a tight n/4 upper and lower bound. In this paper, we further extend the problem and give nontrivial upper and lower bounds. |
| キーワード(和) | オンライン問題 / オンラインアルゴリズム / 競合比 / オンライン独立頂点集合問題 |
| キーワード(英) | online problems / online algorithms / competitive ratio / online independent set problem |
| 資料番号 | COMP2000-4 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/4/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 一般化されたオンライン独立頂点集合問題の競合化 |
| サブタイトル（和） | |
| タイトル（英） | Generalized Online Independent Set Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | オンライン問題 / online problems |
| キーワード(2)（和/英） | オンラインアルゴリズム / online algorithms |
| キーワード(3)（和/英） | 競合比 / competitive ratio |
| キーワード(4)（和/英） | オンライン独立頂点集合問題 / online independent set problem |
| 第 1 著者 氏名（和/英） | 武富 史郎 / Shiro Taketomi |
| 第 1 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 宮崎 修一 / Shuichi Miyazaki |
| 第 2 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 3 著者 氏名（和/英） | 岩間 一雄 / Kazuo Iwama |
| 第 3 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 4 著者 氏名（和/英） | Halldorsson Magnus M. / Magnus M. Halldorsson |
| 第 4 著者 所属（和/英） | アイスランド大学:Taeknigardur University of Iceland Science Institute, University of Iceland:Taeknigardur University of Iceland |
| 発表年月日 | 2000/4/26 |
| 資料番号 | COMP2000-4 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 25 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |