小野 孝男   Takao ONO

講座・コース 情報処理工学講座 Takao ONO
役職 准教授
生年月 1970年07月生
自室番号 2608
Email onotakao**c.oka-pu.ac.jp
※利用の際は,** を @に置き換えてください.
学歴 名古屋大学工学部情報工学科(1993年3月卒業)
名古屋大学大学院博士課程前期課程工学研究科情報工学専攻(1995年3月修了)
名古屋大学大学院博士課程後期課程工学研究科情報工学専攻(1998年3月単位取得退学)
学位 博士(工学),名古屋大学,1999年3月,充足最大化問題の近似アルゴリズムに関する研究
着任年月 2008年09月
職歴 名古屋大学大学院情報科学研究科助教(1998年10月~2008年8月)
専門分野 情報科学
所属学協会 情報処理学会,日本オペレーションズリサーチ学会,IEEE,ACM
現在の研究テーマ 近似アルゴリズムの設計と解析,ヒューリスティックアルゴリズム
主要担当科目
 学部 データ構造とアルゴリズム, プログラミング技法 <プログラミング言語Ⅰ>, 離散数学, 情報通信工学実験ⅡB
 大学院 近似アルゴリズム論
相談・共同研究可能
なテーマ
数理計画法(最適化)
研究概要 われわれが日常直面する問題の中には,離散最適化問題として定式化されるものも多い.しかし,離散最適化問題の多くは NP-困難であり,従って現実的な時間で最適解を求めるアルゴリズムは存在しないと考えられている.一方,実社会においては十分に良い解,すなわち近似解が求まればよいことが普通である.そこで,特にグラフ上の NP-困難な最適化問題に対し近似アルゴリズムの設計と理論的な解析を行う.また,高性能なヒューリスティックアルゴリズムの開発も行う.
【1】 近似アルゴリズムの設計と解析
NP-困難な最適化問題に対して近似アルゴリズムを設計し,その実行時間や近似率(最適解と得られる近似解のコストの比)を理論的に解析する.
たとえば,最大重み独立集合問題に対して新たな解析を与えた.この問題は各頂点が正の重みを持つグラフが与えられたときに,独立集合でその要素である頂点の重みの和が最大となるものを見つける問題である.
この問題に対する研究はこれまでにもなされているが,グラフの平均次数を用いた近似率の解析はなされていなかった.
本研究では重みを考慮した平均次数を導入し,これを用いて近似率の解析を行った.その結果,重みを持たない問題に対する解析を自然な形で拡張することに成功した.
また,入力されるグラフの形状に条件がある場合には,その条件を加味することによりより最適に近い近似解が得られることも示すことができた.
【2】 ヒューリスティックアルゴリズム
頂点彩色問題とは,無向グラフが与えられたときに,辺で隣接する頂点同士が同色にならないように各頂点に色を割り当て,用いる色数を最小とする問題である.
この問題は無線基地局に対する周波数割り当てや講義の教室割り当てなど,多くの割り当て問題に応用することができ実用的にも重要である.しかし,理論的には非常に難しい問題であり,ヒューリスティックアルゴリズムの研究が広く行われている.
本研究では,「半定値計画法」と呼ばれる数理計画法の手法を用いた理論的なアルゴリズムをもとにヒューリスティックアルゴリズムを構築した.得られた問題の理論的な困難性は元の頂点彩色問題と変わらないが,連続量に対する最適化問題となるため,既に知られているいろいろな最適化手法を適用することができる.
現在のところ非常に単純な最適化手法である山登り法を用いているだけであるが,実験的には良い性能を持つことが示せた.
社会における活動 日本オペレーションズリサーチ学会中国四国支部運営委員
最終更新日 2015.05.29