| [ 長期研究 ] |
- テーマ
- NP困難最適化問題の近似不可能性
|
- 内容
-
NP困難最適化問題は、多項式時間で最適解を求めることが不可能であると一般に信じられている。しかし、ある種の問題に関しては、近似アルゴリズムによって近似解を多項式時間で求めることができる。この研究では、その近似アルゴリズムの近似限界について考察することにより、NP困難最適化問題の性質についての理解を深めていく。
|
| [ 短期研究 ] |
- テーマ
- APX-hardなNP困難最適化問題の近似困難比率について
|
- 内容
- APX-hardなNP困難最適化問題の近似困難比率は定数である。すなわち適切な近似アルゴリズムによって、定数近似が保証される。この研究では、さまざまな APX-hard な NP困難最適化問題の近似困難比率を求め、この種の問題の近似アルゴリズム開発の限界を明らかにしていくことを目標とする。
|
| [ 趣味・特技など ] |
旅行、スキューバダイビング |
| [ 皆様へメッセージ ] |
「今だから出きる」ことを探して行きましょう。 |
