| 講演名 | 1999/4/23 オンライン問題の複雑さの解析について 内田 敦, 宮崎 修一, 岩間 一雄, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿ではOnline MWSAT, Online MWISという2つのオンライン問題を導入し, これらの問題が以下の2つの意味で最も困難なオンライン問題であることを示す. (i)これらの問題は, 任意のオンライン問題を模倣可能である. (ii)これらの問題は, より強力なオンラインアルゴリズム(複数の解を同時に保持することを許されたオンラインアルゴリズム)によっても, 最悪の競合比しか得られない. 証明には, NP最適化問題の完全性の証明を利用した. 即ち, オンライン問題を非決定性チューリング機械で定式化し, それをOnline MWSATが模倣可能であることを示した. |
| 抄録(英) | In this paper, we give two online problems, Online MAX WEIGHTED SAT and Online MAX WEIGHTED INDEPENDENT SET, which are hardest in the following two senses: (i) These problems can simulate all online problems without worsening the competitive ration at all. (ii) We can show that the lower bound of the competitive ration for these problems is the worst possible even if we can use probably the most powerful online algorithm (an algorithm which can hold many intermediate solutions simultaneously). |
| キーワード(和) | オンライン問題 / オンラインアルゴリズム / 競合比 |
| キーワード(英) | online problems / online algorithms / competitive ratio |
| 資料番号 | COMP99-8 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/4/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | オンライン問題の複雑さの解析について |
| サブタイトル（和） | |
| タイトル（英） | On the Analysis of the Complexity of Online Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | オンライン問題 / online problems |
| キーワード(2)（和/英） | オンラインアルゴリズム / online algorithms |
| キーワード(3)（和/英） | 競合比 / competitive ratio |
| 第 1 著者 氏名（和/英） | 内田 敦 / Atsushi Uchida |
| 第 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 |
| 発表年月日 | 1999/4/23 |
| 資料番号 | COMP99-8 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 30 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |