文字サイズ
検索

学部・大学院

ホーム > 学部・大学院 > 教員紹介 > 情報・知能工学系 > 木村 慧(きむら けい)

木村 慧(きむら けい)

所属 情報・知能工学系
兼務
職名 助教
専門分野 離散最適化 / アルゴリズム
学位 博士(情報理工学)(東京大学)
所属学会 日本オペレーションズ・リサーチ学会 / 電子情報通信学会
E-mail kimura@cs
※アドレスの末尾に「.tut.ac.jp」を補完してください
研究室web http://www.algo.cs.tut.ac.jp/
研究者情報リンク 研究者情報

研究紹介

制約充足問題とは与えられた制約を満たす,有限個の値をとる離散的な変数への値の割当てを求める問題である.この問題は工学に現れる多くの問題を含むことが知られており,様々な分野で研究がなされている.例えば,充足可能性問題やグラフ彩色問題,整数線形不等式系の実行可能性判定といった,人工知能や理論計算幾何学などの分野における基本的かつ重要な問題を含んでいる.このように重要な問題であるため,制約充足問題を解くためのアルゴリズムに関する研究は古くから行われており,現在もなお盛んに研究が行われている.一方で,制約充足問題は一般にはNP困難であり,そのため,この問題をすべての入力に対して効率的に解くアルゴリズムを開発することは難しいと考えられている.そこで,効率的に解ける部分クラスを明らかにする研究が数多く行われている.近年,扱える制約の種類を制限した問題が(PとNPが異なるという仮定の下で)効率的に解けるための必要十分条件が明らかとなった.本研究の目的は,この結果を踏まえて,様々な問題に対する計算複雑さを明らかにすることである.

主な業績:

Norie Fu, Naonori Kakimura, Kei Kimura, Vorapong Suppakitpaisarn:
Maximum Lifetime Coverage Problem with Battery Recovery Effect,
Sustainable Computing: Informatics and Systems, 18, pp. 1-13, 2018.

Kei Kimura and Kazuhisa Makino:
Autark assignments of Horn CNFs,
Japan Journal of Industrial and Applied Mathematics, 35, pp. 297-309, 2018.

Kei Kimura and Kazuhisa Makino:
Linear Satisfiability Preserving Assignments,
Journal of Artificial Intelligence Research, 61, pp. 291-321, 2018.

Kei Kimura and Kazuhisa Makino:
Trichotomy for Integer Linear Systems Based on Their Sign Patterns,
Discrete Applied Mathematics, 200, pp. 67-78, 2016.


ページトップへ