|
|
|||||
| 2006年度 パッヘ研究奨励金Ⅰ-A-２（特定研究助成・一般）研究成果報告書 | |||||
|
|
|||||
| 氏名 | 大月 英明 | 所属 | 数理情報学部情報通信学科 | ||
| 研究課題 | ＮＰ 困難な最適化問題の近似不可能性についての研究 | ||||
| 研究実績の概要 | |||||
| ２００６年度も昨年に引き続き「ＮＰ 困難な最適化問題の近似不可能性」についての研究をおこなった。具体的な内容は以下のとおりである。 ＮｘＭ のブール行列をＮｘＲ とＲｘＭ の２つのブール行列の積に分解した際、Ｒを最小の値にする問題はＮＰ困難であることが証明されている。Ｒはブール行列のランクと呼ばれることがある。本研究ではこの問題から派生した新しいＮＰ困難な問題Ｐを提唱した。 問題Ｐとは、まずランクの値Ｒを固定し、その積の行列要素のうち、元の行列要素と一致しない要素を最小化する（一致する要素数を最大化する)２つの行列を求める問題である。さらに、一致しない要素数を最小にするＮＰ困難な最適化問題ＯＰを考えることもできる。 しかし、近年の研究発表の傾向として、ＮＰ困難性を証明しただけでは若干新規性に乏しいとされることが多い。そこで今後の計画として、この問題の具体的な近似可能性、ＮＰ困難な近似比率の下界を求めるなどし、学会発表ならびに研究成果の刊行を行う予定である。 |
|||||
| 「雑誌」の部 | 「図書」の部 | ||||
| ① | 論文題目 | ① | 書名 | ||
| 雑誌名 | 出版社 | ||||
| 巻号 | 論文名 | ||||
| 発表年月 | 発表年月 | ||||
| ページ | ページ | ||||
| 著者名 | 著者名 | ||||
| 備考 | 備考 | ||||
| ② | 論文題目 | ② | 書名 | ||
| 雑誌名 | 出版社 | ||||
| 巻号 | 論文名 | ||||
| 発表年月 | 発表年月 | ||||
| ページ | ページ | ||||
| 著者名 | 著者名 | ||||
| 備考 | 備考 | ||||
| ③ | 論文題目 | ③ | 書名 | ||
| 雑誌名 | 出版社 | ||||
| 巻号 | 論文名 | ||||
| 発表年月 | 発表年月 | ||||
| ページ | ページ | ||||
| 著者名 | 著者名 | ||||
| 備考 | 備考 | ||||