情報工学科・専攻

理工学部情報工学科教授 今堀慎治が国際スケジューリングシンポジウムにおいて最優秀論文賞を受賞

2015年07月13日

授賞式のようす(写真右が今堀慎治教授)

情報工学科教授 今堀慎治が International Symposium on Scheduling 2015(国際スケジューリングシンポジウム)において発表した論文「A 1+O(1/n) approximation algorithm for TTP(2)(巡回トーナメント問題に対する1+O(1/n)近似アルゴリズム)」が Best Paper Award for Scheduling Theory(最優秀論文賞(スケジューリング理論部門))を受賞しました。

本論文で扱った TTP(巡回トーナメント問題)とは、サッカーの Jリーグのように、与えられた nチームそれぞれが、他の n-1チームとホーム&アウェイで1試合ずつ対戦するスケジュール(総当たりリーグ戦の対戦表)を作成する問題です。

本論文ではホーム&アウェイのバランスなどの制約条件を満たしながら、全てのチームの移動距離の総和ができるだけ短い対戦表を作成するアルゴリズムを提案し、既存の手法で得られるスケジュールの総移動距離を大幅に短縮することに成功しました。