2005年度　パッヘ研究奨励金Ⅰ-A-２（特定研究助成・特別）研究成果報告書
　　
氏名 大月　英明 所属 数理情報学部情報通信学科
研究課題 NP困難な最適化問題の近似不可能性についての研究

研究実績の概要
研究経過
　NP困難な最適な問題のうち，グラフの変形にかかわる問題についてその近似不可能性について研究を行った．そのような問題の中で，辺縮約問題に関しての近似不可能な比率の下界を求めることができた．
研究結果
　(1) 辺縮約問題に関して，１に限りなく近い近似比率で解く近似アルゴリズムは存在しないことを証明した．近似が不可能な比率の下界はおおよそ1.0000285となり，これよりも良い近似は多項式時間では不可能である（P＝NPでない限り）．
　(2) また一般のグラフだけではなく，問題のグラフを２部グラフに限ってもやはり近似比率の下界は有界であることを証明した．
　これらの結果は，辺縮約問題は近似することが比較的困難な問題に分類される，ということを示している．
　結果の一部は2005 Japan-Korea Joint Workshop on Algorithms and Computationなどで学会発表し，論文は電子情報通信学会誌「離散数学とその応用小特集号」に掲載予定である．

「雑誌」の部 「図書」の部
① 論文題目 「辺縮約問題の近似困難性」 ① 書名  
雑誌名 『情報科学技術レターズ』 出版社  
巻号 第４巻 巻号  
発表年月 2005年９月 発表年月  
ページ pp.17～20 ページ  
著者名 大月　英明/平田　富夫 著者名  
備考 抜刷提出 備考  
② 論文題目 “Inapproximability of the edge-contraction problem” ② 書名  
雑誌名 『離散数学とその応用小特集号』 出版社  
巻号 Vol. E89-A 巻号  
発表年月 2006年５月 発表年月  
ページ   ページ  
著者名 Hideaki Otsuki/Tomio Hirata 著者名  
備考 刊行予定（掲載受理済） 備考  
③ 論文題目   ③ 書名  
雑誌名   出版社  
巻号   巻号  
発表年月   発表年月  
ページ   ページ  
著者名   著者名  
備考   備考