NMR量子計算の定式化
スポンサーリンク
概要
- 論文の詳細を見る
NP完全である時間割決定問題に対して一つの最適化版を定義し, それがある制限の下でAPX完全であることを示した.すなわち, 1週間に存在するコマの集合, 各教師の授業可能なコマの集合, 各クラスが授業を受けることの可能なコマの集合, 各教師が各クラスに1週間に行う授業の回数, が与えられたときに, それらの条件に矛盾しない範囲で, なるべくたくさんの教師を割り当てた時間割を求めるという問題を考え, さらに, 一人の教師が授業をするクラス数, 一つのクラスが授業を受ける教師数を共にk以下とする制限を導入したところ, このような制限付き時間割最適化問題はAPX困難であり, k(k-1)+1近似アルゴリズムを持つことを示した.すなわち, それがAPX完全であることが示された。
- 社団法人電子情報通信学会の論文
- 1998-03-24