充足最大化問題の近似アルゴリズムに関する研究
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
充足最大化問題の近似アルゴリズムに関する研究
- 著者名
-
小野, 孝男
- 著者別名
-
オノ, タカオ
- 学位授与大学
-
名古屋大学
- 取得学位
-
博士(工学)
- 学位授与番号
-
甲第4332号
- 学位授与年月日
-
1999-03-25
注記・抄録
博士論文
目次
- 目次 / p1 (0003.jp2)
- 第1章 序論 / p1 (0005.jp2)
- 1.1 はじめに / p1 (0005.jp2)
- 1.2 充足最大化問題 / p3 (0006.jp2)
- 第2章 理論的背景 / p7 (0008.jp2)
- 2.1 諸定義 / p8 (0009.jp2)
- 2.2 PTAS / p9 (0009.jp2)
- 2.3 MAX SNP-完全性 / p10 (0010.jp2)
- 2.4 近似不可能性の理論 / p15 (0012.jp2)
- 第3章 3-充足最大化問題に対する近似アルゴリズム / p21 (0015.jp2)
- 3.1 近似アルゴリズムの構築 / p22 (0016.jp2)
- 3.2 近似性能の理論的評価 / p38 (0024.jp2)
- 3.3 決定性アルゴリズムへの変換 / p40 (0025.jp2)
- 3.4 まとめと考察 / p48 (0029.jp2)
- 第4章 充足最大化問題に対する近似アルゴリズム / p49 (0029.jp2)
- 4.1 近似アルゴリズムの構築 / p49 (0029.jp2)
- 4.2 近似性能の理論的評価 / p52 (0031.jp2)
- 4.3 摂動法による近似アルゴリズムの改良 / p52 (0031.jp2)
- 4.4 決定性アルゴリズムへの変換 / p60 (0035.jp2)
- 4.5 まとめと考察 / p61 (0035.jp2)
- 第5章 近似アルゴリズムの実際的評価 / p63 (0036.jp2)
- 5.1 従来の近似アルゴリズムの実験的性能比較 / p64 (0037.jp2)
- 5.2 半定値緩和アルゴリズムの実験的性能評価 / p72 (0041.jp2)
- 5.3 まとめと考察 / p74 (0042.jp2)
- 第6章 あとがき / p81 (0045.jp2)
- 謝辞 / p83 (0046.jp2)
- 参考文献 / p85 (0047.jp2)