| 講演名 | 1998/3/24 NMR量子計算の定式化 竹内 光一, 守屋 悦郎, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | NP完全である時間割決定問題に対して一つの最適化版を定義し, それがある制限の下でAPX完全であることを示した.すなわち, 1週間に存在するコマの集合, 各教師の授業可能なコマの集合, 各クラスが授業を受けることの可能なコマの集合, 各教師が各クラスに1週間に行う授業の回数, が与えられたときに, それらの条件に矛盾しない範囲で, なるべくたくさんの教師を割り当てた時間割を求めるという問題を考え, さらに, 一人の教師が授業をするクラス数, 一つのクラスが授業を受ける教師数を共にk以下とする制限を導入したところ, このような制限付き時間割最適化問題はAPX困難であり, k(k-1)+1近似アルゴリズムを持つことを示した.すなわち, それがAPX完全であることが示された。 |
| 抄録(英) | We define an optimization version of an NP-complete problem, the school timetable problem. In this problem, we are given a set of class hours in a week, a set of possible class hours for each teacher to teach, a set of possible class hours for each class to be taught, and the number of class hours for each teacher to teach each class in a week. The problem is to find a timetable that is assigned as many teachers as possible without contradicting to above-mentioned condition. If we introduce a restriction both the number of classes a teacher teaches, for and the number of teachers each class are equal to or less than k, then the timetable optimization problem with this restriction is APX-hard, and has an approximation algorithm with a ratio bound of k(k-1)+1. Thus the problem is APX-complete. |
| キーワード(和) | NP最適化問題 / 時間割 / APX困難 / APX完全 |
| キーワード(英) | NP optimization problem / timetable / APX-hard / APX-complete |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/3/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | NMR量子計算の定式化 |
| サブタイトル（和） | |
| タイトル（英） | An optimization version of the timetable problem is APX-complete |
| サブタイトル（和） | |
| キーワード(1)（和/英） | NP最適化問題 / NP optimization problem |
| キーワード(2)（和/英） | 時間割 / timetable |
| キーワード(3)（和/英） | APX困難 / APX-hard |
| キーワード(4)（和/英） | APX完全 / APX-complete |
| 第 1 著者 氏名（和/英） | 竹内 光一 / Kouichi TAKEUCHI |
| 第 1 著者 所属（和/英） | 早稲田大学理工学研究科数理科学専攻 Department of Mathematics Graduate School of Science and Engineering Waseda University |
| 第 2 著者 氏名（和/英） | 守屋 悦郎 / Etsuro MORIYA |
| 第 2 著者 所属（和/英） | 早稲田大学教育学部数学教室 Department of Mathematics School of Education Waseda University |
| 発表年月日 | 1998/3/24 |
| 資料番号 | |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 628 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |