本論文は，対戦日程計画に関する多項式時間解法の研究について記したものである．対戦日程計画とはスケジューリングの一分野であり，主にスポーツ競技に使用される形式のスケジューリング問題を扱う．本研究では対戦日程計画のうち，Home-Away Table 許容性判定問題とブレーク数最小化問題の二つに対して数理的な解析を行い，いくつかの多項式時間解法を構築した．

スポーツ競技の総当りリーグ戦では，「各チームが相異なる本拠地を持ち，それぞれの試合は対戦するチームのどちらかの本拠地で行う」という対戦形式が頻繁に用いられる．Home-Away Table 許容性判定問題とブレーク数最小化問題はどちらもこのリーグ戦形式のスケジューリング問題であり，実用的な観点からも効率的な解法の構築が望まれている．

上記の形式の総当りリーグ戦においては，各試合の開催場所はスケジュールの質に関わる重要な要素であり，しばしばスケジューリングの際に制約条件として与えられる．これら試合開催場所に関する制約条件は，Home-Away Table と呼ばれている．Home-Away Table 許容性判定問題は，与えられたHome-Away Table に従うスケジュールが作成可能か判定する問題である．従来この問題に対しては整数計画法や制約論理法を用いた解法が提案されていたが，現在のところ多項式時間解法は知られておらず，問題の計算複雑度も解明されていない．本研究ではHome-Away Table許容性判定問題に対して，与えられたHome-Away Tableからスケジュールを生成できるための必要条件を新たに提案した．この必要条件は問題のサイズに対して指数本の不等式で表現されるが，実用的に重要とされているHome-Away Tableのクラスに対しては，この必要条件が多項式時間で評価できることを証明した．またこれらのHome-Away Tableの許容性判定において，提案した必要条件が極めて有効であることを計算機実験によって示した．

総当りリーグ戦のスケジューリングでは，各チーム間の対戦順序が制約条件として与えられるケースもある．この場合には，与えられた対戦順序を満たし，かつ質の良いスケジュールの作成が求められる．一般にスケジュールの質を測る指標の一つとして「ブレーク数」と呼ばれるものが用いられており，実用上の理由からブレーク数が小さいスケジュールが望ましいとされている．ブレーク数最小化問題は，各チーム間の対戦順序が制約条件として与えられた時に，ブレーク数が最小となるスケジュールを作成する最適化問題である．この問題に対しては制約論理法や整数計画法などによる厳密解法が提案されているが，これらの手法では問題の規模が大きくなると計算時間が急激に増大し最適解を求めるのが困難になる．本研究では，ブレーク数最小化問題のMAX RES CUTとしての定式化およびMAX 2SATとしての定式化を提案した．これらの定式化により，MAX RES CUTあるいはMAX 2SATに対する多項式時間近似アルゴリズムをブレーク数最小化問題に適用することが可能となる．本研究では，半正定値計画緩和に基づいたGoemans, Williamsonの多項式時間近似アルゴリズムを採用し，ブレーク数最小化問題の許容解を生成する多項式時間アルゴリズムを実装した．さらに計算機実験によって，サイズの大きな問題例に対しても質の良い許容解が高速に生成できることを実証した．一方で，ブレーク数最小化問題の計算複雑度は明らかになっておらず，一般の場合についての多項式時間解法は知られていない．しかしながら2003年にElf, Junger, Rinaldiによって「最適解のブレーク数がリーグ戦のチーム数未満になるインスタンスに対しては，多項式時間でブレーク数最小化問題の最適解を求めることが可能である」という予想が提示されていた．本研究では，最適解のブレーク数がリーグ戦のチーム数以下となるインスタンスに対して，ブレーク数最小化問題の最適解を求める多項式時間アルゴリズムを開発した．この結果により，前述した予想に対する肯定的な解決を与えた．

本論文は，対戦日程計画に関する多項式時間解法に関する研究である．対戦日程計画とはスケジューリングの一分野であり，主にスポーツ競技に使用される形式のスケジューリング問題を扱う分野である．本論文では対戦日程計画のうち，Home-Away Table許容性判定問題とブレーク数最小化問題の二つに対して数理的な解析を行い，いくつかの多項式時間解法を構築している．

スポーツ競技の総当りリーグ戦では，「各チームが相異なる本拠地を持ち，それぞれの試合は対戦するチームのどちらかの本拠地で行う」という対戦形式が頻繁に用いられる．Home-Away Table許容性判定問題とブレーク数最小化問題はどちらもこのリーグ戦形式のスケジューリング問題であり，実用的な観点からも効率的な解法の構築が望まれている．上記の形式の総当りリーグ戦においては，各試合の開催場所はスケジュールの質に関わる重要な要素であり，しばしばスケジューリングの際に制約条件として与えられる．これら試合開催場所に関する制約条件は，Home-Away Tableと呼ばれている．Home-Away Table許容性判定問題は，与えられたHome-Away Tableに従うスケジュールが作成可能か判定する問題である．従来この問題に対しては整数計画法や制約論理法を用いた解法が提案されていたが，現在のところ多項式時間解法は知られておらず，問題の計算複雑度も解明されていない．

本論文第2章ではHome-Away Table許容性判定問題に対して，与えられたHome-Away Tableからスケジュールを生成できるための必要条件が新たに提案されている．この必要条件は問題のサイズに対して指数本の不等式で表現されるが，実用的に重要とされているHome-Away Tableのクラスに対しては，この必要条件が多項式時間で評価できることを証明している．またこれらのHome-Away Tableの許容性判定において，提案した必要条件が極めて有効であることを計算機実験によって示している．

本論文後半では，ブレーク数最小化問題について扱っている．総当りリーグ戦のスケジューリングでは，各チーム間の対戦順序が制約条件として与えられるケースもある．この場合には，与えられた対戦順序を満たし，かつ質の良いスケジュールの作成が求められる．一般にスケジュールの質を測る指標の一つとして「ブレーク数」と呼ばれるものが用いられており，実用上の理由からブレーク数が小さいスケジュールが望ましいとされている．ブレーク数最小化問題は，各チーム間の対戦順序が制約条件として与えられた時に，ブレーク数が最小となるスケジュールを作成する最適化問題である．この問題に対しては制約論理法や整数計画法などによる厳密解法が提案されているが，これらの手法では問題の規模が大きくなると計算時間が急激に増大し最適解を求めるのが困難になる．

本論文第3章では，ブレーク数最小化問題のMAX RES CUTとしての定式化およびMAX 2SATとしての定式化を提案している．これらの定式化により，MAX RES CUTあるいはMAX 2SATに対する多項式時間近似アルゴリズムをブレーク数最小化問題に適用することが可能となる．3.3節では，半正定値計画緩和に基づいたGoemans, Williamsonの多項式時間近似アルゴリズムを採用し，ブレーク数最小化問題の許容解を生成する多項式時間アルゴリズムを実装している．さらに計算機実験によって，サイズの大きな問題例に対しても質の良い許容解が高速に生成できることが確認されている．一方で，ブレーク数最小化問題の計算複雑度は明らかになっておらず，一般の場合についての多項式時間解法は知られていない．しかしながら2003年にElf, Juenger, Rinaldiによって「最適解のブレーク数がリーグ戦のチーム数未満になるインスタンスに対しては，多項式時間でブレーク数最小化問題の最適解を求めることが可能である」という予想が提示されていた．3.2節では，最適解のブレーク数がリーグ戦のチーム数以下となるインスタンスに対して，ブレーク数最小化問題の最適解を求める多項式時間アルゴリズムを開発している．この結果により，前述した予想に対する肯定的な解決が与えられた．

以上の諸結果は数理情報学の発展に大きく寄与するものであり高く評価できる．

よって本論文は博士（情報理工学）の学位請求論文として合格と認められる．