試問予定表作成問題の計算複雑さ
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,試問予定表作成問題と呼ばれる大学における時間割表作成問題を考える.この問題では,m人の審査員の集合,2n人の学生の集合,各学生について審査する複数の審査員の担当割当(例えば各学生を3人ずつの審査員が担当)が与えられる.審査はn人ずつ2つの部屋で同時に行われるため,学生と担当審査員の組は,n個の時刻と2つの部屋から成るn×2行列に割り当てられる必要がある.ここで,同じ審査員が担当する異なる2人の学生は異なる時刻に割り当てられなければならない.さらに,すべての審査員が2つの部屋を移動する回数の合計をできるだけ少なくしたい.本問題は,実際に京都大学の試問予定表作成時に起きた問題を形式化したものである.この問題について2つの制約付きモデルを提案し,それらの計算複雑さについて調査する.
- 社団法人電子情報通信学会の論文
- 2006-06-16
著者
関連論文
- 片方のみがタイを持つ安定結婚問題に対する25/17近似アルゴリズム (アルゴリズムと計算機科学の数理的基盤とその応用)
- 最大サイズ最大安定度マッチング問題に対する近似下限の改良
- 直径d部分グラフ最大化問題の計算複雑さ
- 枝コストに制限を加えたk-Canadian Traveller Problemの競合比解析 (コンピュテーシヨン)
- 安全なギガビットネットワークシステムKUINS-IIIの構成とセキュリティ対策(ネットワーク管理)(インターネットアーキテクチャ技術論文)
- 安全なギガビットネットワーク(KUINS-3)の構築と運用
- BS-8-11 2部グラフ上での分担供給可能な割当て制限付き資源配分問題(BS-8.情報通信とエネルギー管理の統合技術,シンポジウムセッション)
- 最大出次数最小化問題の各種グラフクラスに対する計算複雑さ
- 直径d部分グラフ最大化問題の近似について
- 完全二分木の直線埋め込みについて
- マジックプロトコル利用によるプライバシーに配慮したShibboleth属性交換の拡張
- マジックプロトコル利用によるプライバシーに配慮したShibboleth属性交換の拡張
- 最大支配問題
- グラフの最小出次数最大化問題
- 最小マンハッタンネットワーク問題の近似について (理論計算機科学の深化と応用)
- QoSネットワーク上のマルチキュースイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良析
- 最小ブロック転送問題の近似可能性と近似不可能性
- 第三者機関の仲介を必要としない配達証明付き電子メールシステムの設計(学生セッション,学生セッション,一般)
- 男女平等安定マッチング問題に対する近似アルゴリズム
- 長さ2のタイを含む安定結婚問題に対する近似アルゴリズム
- LA-7 ランダムタイブレークによる安定マッチングの導出(A. アルゴリズム・基礎)
- バンプ探索における解の精度(セッション1)
- バンプ探索における解の精度(セッション1)
- 一般化されたオンライン独立頂点集合問題の競合化
- 安定結婚問題の近似可能性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 座席予約問題における競合比の上下限の改良 (Theoretical foundations of computing)
- DS-1-6 オンラインOVSF符号割当問題における競合比の上下限の改良(DS-1. COMP学生シンポジウム,シンポジウムセッション)
- 2ポート共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの厳密な競合比解析
- マルチキュースイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良(計算理論とアルゴリズムの新展開)
- 共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良
- 配属人数下限付き研修医配属問題 (理論計算機科学の深化と応用)
- 3人部屋安定ルームメイト問題のNP完全性
- DS-1-3 安定結婚問題に対する1.8-近似アルゴリズム(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 安定結婚問題に対する1.875-近似アルゴリズム
- 枝コストに制限を加えたk-Canadian Traveller Problemの競合比解析
- 安定マッチング問題に関する最近の話題(「社会的インタラクションにおける知」及び一般)
- 段階的秘密交換プロトコルを利用した配達内容証明が可能な電子メール配送システム設計上の検討(学生セッション)
- サイクル上でのグラフ探索問題に対する最適なオンラインアルゴリズム
- サイクルグラフ上での地図作成問題に対する重み付き最近傍アルゴリズム
- 試問予定表作成問題の計算複雑さ
- 不正を検出できるネットワーク軍人将棋
- 移動物体回収問題 : ロボットに効率良く物体を回収させるアルゴリズムの設計のために(学生/教養のページ)
- 移動物体回収問題
- ブックマーク問題の近似について
- 一様メトリックにおけるソーティングバッファ問題のNP困難性
- 顧客データベースにおけるbump huntingとその精度
- バンプ探索における解の精度
- 最大重み付き出次数を最小化するグラフ有向化問題の近似(不)可能性
- Bump hunting 問題における極値統計の応用(日本計算機統計学会 第19回シンポジウム)
- 最大出次数を最小化するグラフ有向化について
- 期限付き移動物体に対する回収アルゴリズム
- 資源増加を許したOVSF符号割当問題に対する2競合アルゴリズム
- SATに対する局所探索法のベクトル化
- SATに対する局所探索法のベクトル化
- 局所探索法による安定結婚問題の近似
- D-1-2 安定結婚問題に対する局所探索近似アルゴリズム(D-1. コンピュテーション)
- 枝コストに制限を加えた k-Canadian Traveller Problem の競合比解析
- 頂点数を最大とする正則誘導連結部分グラフ問題の計算複雑さ (コンピュテーンョン)
- 安定結婚問題に対する局所探索近似アルゴリズムの改良
- 資源増加を許したOVSF符号割当問題に対する(1 + ε)-競合アルゴリズム
- 座席予約問題における競合比の上下限の改良
- 第三者機関の仲介を必要としない配達証明付き電子メールシステムの設計
- 2.ルータ上のバッファ管理問題に対するオンラインアルゴリズム(インターネットとアルゴリズム)
- 安定結婚問題
- D-1-4 最大化および最小化アルゴリズムにおける近似度の関係
- PVMによるSAT並列局所探索プログラム
- PVMによるSAT並列局所探索プログラム
- 鳩の巣原理に対する木状導出原理の証明サイズの上下限の改良 (新しいパラダイムとしてのアルゴリズム工学)
- 最大支配問題
- タイル縁に上書きルールを用いた敷き詰め問題
- タイル縁に上書きルールを用いた敷き詰め問題
- 効率の良い罫線描画について
- 折線上を移動する物体に対する回収問題の困難性
- 期限付き移動物体に対する回収アルゴリズム
- 移動系における最大個数巡回アルゴリズム (計算機科学基礎理論の新展開)
- 容量を制限した場合の移動物体巡回問題 (計算機科学基礎理論の新展開)
- 頂点数を最大とする正則誘導連結部分グラフ問題の計算複雑さ
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- PS-106-6 人工血管壁への細菌侵入に関する研究 : エラストマーシールドダクロングラフトとゼラチンコーティングダクロングラフトにおける検討(PS-106 心血管 基礎,ポスターセッション,第112回日本外科学会定期学術集会)
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- ターミナル数5の成分素シュタイナー木最大化問題に対する近似アルゴリズム
- 距離d独立頂点集合問題の計算複雑さ
- DS-1-1 希望リスト変更による男性最良安定マッチングの改善(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 次数指定した最大正則誘導部分グラフ探索問題(一般)
- 同一の送受信アドレスを持つ大量メールの効率判定手法(認証とセキュリティ,インターネットと情報倫理教育,一般)