Home>トピックニュース＞2015/04/07

2015.04.07

社会工学専攻 河瀬康志助教が電子情報通信学会 学術奨励賞を受賞しました。

社会工学専攻 河瀬康志助教が平成26年度 電子情報通信学会 学術奨励賞を受賞しました。
授賞式が、3月11日に電子情報通信学会 総合大会（於：立命館大学）にて行われました。


・電子情報通信学会 学術奨励賞
　河瀬康志
　「最適合成順問題」
　　　（京都大学 牧野和久氏，トーア再保険株式会社 勢見賢人氏との共同研究）



　　平成26年度学術奨励賞受賞式にて（右より２人目が河瀬氏）



本研究では、最適合成順問題を導入し、その計算複雑性を議論した。入力としてn個の実関数f1,...,fnと実数cが与えられる。このとき、最大全合成順問題はfσ(n) ◦ fσ(n-1) ◦ … ◦fσ(1)(c)を最大化するn次の置換σを求める問題である。最大部分合成順問題はfσ(k) ◦ fσ(k-1) ◦ … ◦fσ(1)(c)を最大化するn次の置換σと非負整数k (0≦k≦n)を求める問題である。
本研究では、単調非減少な1次関数に対する最大全合成順問題、最大部分合成順問題に対しO(n log n)時間アルゴリズムを与えた。 また、2区分からなる区分線形単調関数に対する問題の場合でも、どちらもNP困難となることを示した。