2024/09/27 更新

お知らせ

 

写真a

キムラ　ケイ
木村 慧
KIMURA KEI
所属
システム情報科学研究院 情報学部門 准教授
工学部 電気情報工学科（併任）
システム情報科学府 情報理工学専攻（併任）
マス・フォア・イノベーション連係学府 （併任）
職名
准教授
プロフィール
広くは計算機科学，数理工学，応用数学，より詳細には組合せ最適化，離散アルゴリズムの研究に従事
ホームページ
外部リンク

学位

  • 博士（情報理工学）

経歴

  • 九州大学 准教授

    2021年10月 - 現在

    　 詳細を見る

研究テーマ・研究キーワード

  • 研究テーマ：離散最適化

    研究キーワード：離散最適化

    研究期間： 2024年

  • 研究テーマ：整数計画

    研究キーワード：整数計画

    研究期間： 2024年

  • 研究テーマ：制約充足問題

    研究キーワード：制約充足問題

    研究期間： 2024年

  • 研究テーマ：アルゴリズム

    研究キーワード：アルゴリズム

    研究期間： 2024年

  • 研究テーマ：数理最適化，アルゴリズム，メカニズムデザイン，理論計算機科学

    研究キーワード：整数線形最適化，離散構造，マッチング，計算複雑さ

    研究期間： 2022年6月

受賞

  • 準優秀賞

    2022年3月   SMASH22 WINTER SYMPOSIUM 実行委員会   マルチエージェント経路探索アルゴリズムの 改良のための一検討

  • 準優秀賞

    2022年3月   SMASH22 WINTER SYMPOSIUM 実行委員会   マルチエージェント経路探索アルゴリズムの 改良のための一検討

    柴田航志, 木村慧, 東藤大樹, 横尾真

    　詳細を見る

  • 令和3年度ベストレクチャー賞

    2021年11月   埼玉大学 工学部  

  • 令和2年度ベストレクチャー賞

    2020年12月   埼玉大学 工学部  

  • 系長賞

    2018年11月   豊橋技術科学大学 情報・知能工学系  

  • 最優秀論文賞

    2013年3月   電子情報通信学会   整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標

  • 最優秀発表賞受賞

    2011年6月   日本オペレーションズ・リサーチ学会「計算と最適化の新展開」研究部会   整数線形システムの実行可能性問題に対する計算複雑さの指標

▼全件表示

論文

  • Fairness and efficiency trade-off in two-sided matching.

    Sung-Ho Cho, Kei Kimura, Kiki Liu, Kwei-guu Liu, Zhengjie Liu, Zhaohong Sun 0001, Kentaro Yahiro, Makoto Yokoo

    CoRR   abs/2402.01084   2024年2月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.48550/arXiv.2402.01084

    researchmap

  • Characterizing the integer points in 2-decomposable polyhedra by closedness under operations.

    Kei Kimura, Kazuhisa Makino, Shota Yamada, Ryo Yoshizumi

    CoRR   abs/2401.06405   2024年1月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.48550/arXiv.2401.06405

    researchmap

  • 施設配置ゲームのための Ordered Weighted Average メカニズムにおける操作の非自明性

    吉田 健人, 木村 慧, 東藤 大樹, 横尾 真

    人工知能学会全国大会論文集   JSAI2024 ( 0 )   2F6GS502 - 2F6GS502   2024年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>本発表では，一次元線分上の施設配置ゲーム，すなわち，参加するエージェントが一次元線分上の自分の位置を申告した際に，それらの申告から施設の配置を定める問題を考える．本発表では特に，Ordered Weighted Average メカニズムに着目し，その操作の非自明性について議論する．Ordered Weighted Average メカニズムとは，エージェントの申告の値を昇順に整列し，その順番に従って重みをかけ，その総和を返すようなメカニズムである．本発表では，それぞれの順序にかける重みを変えることにより，操作の非自明性がどのように変化するかを解析する．</p>

    DOI： 10.11517/pjsai.jsai2024.0_2f6gs502

    CiNii Research

  • 整凸関数の線形補間によるL拡張可能性に関する一考察

    横山 健, 岩政 勇仁, 木村 慧, 横尾 真

    人工知能学会全国大会論文集   JSAI2024 ( 0 )   3Xin235 - 3Xin235   2024年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とする．特に，線形補間によるL拡張可能性に着目し，そのような拡張が可能である整凸関数の特徴付けについて議論する．</p>

    DOI： 10.11517/pjsai.jsai2024.0_3xin235

    CiNii Research

  • 情報伝播を伴う施設配置ゲームにおける様々な匿名性

    安東 稜人, 木村 慧, 東藤 大樹, 横尾 真

    人工知能学会全国大会論文集   JSAI2024 ( 0 )   3Xin250 - 3Xin250   2024年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>情報伝播を伴うメカニズムはエージェントにインセンティブを与えできるだけ多くの同僚をメカニズムに参加させることと目的としている．情報伝播を伴う施設配置ゲームは耐戦略性，パレート効率性，匿名性を満たすメカニズムが存在しない不可能性定理が知られており，匿名性を満足しない耐戦略性，パレート効率性を満たすメカニズムが2つ知られている． 我々の目的は耐戦略性，パレート効率性を満たすメカニズムが他に存在するか検証することである． 本論文では匿名性に焦点を当てる．まず分割を導入して部分匿名性を定義し，耐戦略性，パレート効率性を満たすメカニズムが存在する分割の条件を明らかにした．</p>

    DOI： 10.11517/pjsai.jsai2024.0_3xin250

    CiNii Research

  • 学校選択に応用可能な新たな公平性概念の提案

    若杉 天真, 木村 慧, 孫 兆鴻, 横尾 真

    人工知能学会全国大会論文集   JSAI2024 ( 0 )   2F6GS501 - 2F6GS501   2024年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>両方向のマッチング理論は広範囲に発展しており，学生の嫉妬を減少させ，総合的な福祉を向上させるようなマッチングを求めることが望まれている．しかし，効率性と公平性の間にはトレードオフが存在することが明らかになっている．そのため，本研究では，現実の世界で適用可能の一定の公平性を維持することで，効率性を向上させることを考える．我々の貢献はreverse Envy-Freeness up to k peers (r-EF-k; 最大k人の人物からのみ嫉妬を受け得る)と呼ばれるより弱い公平性の要件を提案することである．kを変化させることで，r-EF-kは異なる公平性のレベルを要求することができる．本研究では，一般的な制約下において，r-EF-kおよび効率性を満たすメカニズムについて議論する．</p>

    DOI： 10.11517/pjsai.jsai2024.0_2f6gs501

    CiNii Research

  • ソーシャルネットワーク上での両方向マッチングにおける公平性の緩和

    竹島 遼太, 木村 慧, 横尾 真

    人工知能学会全国大会論文集   JSAI2024 ( 0 )   3Xin2112 - 3Xin2112   2024年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>行動経済学において，人は自分に近い人との比較で幸福度が決定するという仮説が提唱されている．この仮説に従い，本研究では，ソーシャルネットワーク上で直接つながっている相手に対してのみ嫉妬が発生する状況での両方向マッチングを考え，公平性と効率性の関係について検証する．特に，前述のような嫉妬を隣人への嫉妬として，また，隣人への嫉妬が存在しないという性質を局所公平性として定義し，これを従来の公平性の緩和として採用する．そして，マッチング市場における片側の選好を制限することで，隣人への嫉妬がなく（つまり，局所的に公平であり），かつパレート効率的であるマッチングの存在性およびそのようなマッチングを出力するメカニズムについて議論する．</p>

    DOI： 10.11517/pjsai.jsai2024.0_3xin2112

    CiNii Research

  • Parameterized Complexity of Weighted Target Set Selection

    Suzuki, T; Kimura, K; Suzuki, A; Tamura, Y; Zhou, X

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024   14637   320 - 331   2024年   （ ISSN:0302-9743 ISBN:978-981-97-2339-3 eISSN:1611-3349 ）

    　詳細を見る

    出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

    Consider a graph G where each vertex has a threshold. A vertex v in G is activated if the number of active vertices adjacent to v is at least as many as its threshold. A vertex subset A0 of G is a target set if eventually all vertices in G are activated by initially activating vertices of A0. The Target Set Selection problem (TSS) involves finding the smallest target set of G with vertex thresholds. This problem has already been extensively studied and is known to be NP-hard even for very restricted conditions. In this paper, we analyze TSS and its weighted variant, called the Weighted Target Set Selection problem (WTSS) from the perspective of parameterized complexity. Let k be the solution size and ℓ be the maximum threshold. We first show that TSS is W[1]-hard for split graphs when parameterized by k+ℓ, and W[2]-hard for cographs when parameterized by k. We also prove that WTSS is W[2]-hard for trivially perfect graphs when parameterized by k. On the other hand, we show that WTSS can be solved in O(nlogn) time for complete graphs. Additionally, we design FPT algorithms for WTSS when parameterized by nd+ℓ, tw+ℓ, ce, and vc, where nd is the neighborhood diversity, tw is the treewidth, ce is the cluster editing number, and vc is the vertex cover number of the input graph.

    DOI： 10.1007/978-981-97-2340-9_27

    Web of Science

    Scopus

  • 2期間マッチングにおける公平性と非浪費性

    米谷 颯人, 木村 慧, 孫 兆鴻, 横尾 真

    人工知能学会全国大会論文集   JSAI2024 ( 0 )   1I3GS501 - 1I3GS501   2024年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>本論文では，時間の経過に伴い選好が変化する状況を捉えることのできる，2 期間を通じた両方向マッチングを考察する．このようなモデルでは，各期間で異なるエージェントとマッチングすることが可能である．従来の研究では，いずれの期間においても，エージェント一人，あるいはエージェントのペアが結託することで得をするようなことがないマッチングを動的安定なマッチングとして定義している． 本論文では，2 期間マッチングにおける新たな公平性および非浪費性，個人合理性を定義し，動的安定性との関係性について考察する．また，定義した公平性と非浪費性を同時に満たすマッチングの存在性について議論する．</p>

    DOI： 10.11517/pjsai.jsai2024.0_1i3gs501

    CiNii Research

  • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems.

    Kei Kimura, Kazuhisa Makino

    ISAAC   47 - 17   2023年12月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.4230/LIPIcs.ISAAC.2023.47

    researchmap

    その他リンク： https://dblp.uni-trier.de/db/conf/isaac/isaac2023.html#KimuraM23

  • Multi-Stage Generalized Deferred Acceptance Mechanism: Strategyproof Mechanism for Handling General Hereditary Constraints.

    Kei Kimura, Kwei-guu Liu, Zhaohong Sun 0001, Kentaro Yahiro, Makoto Yokoo

    CoRR   abs/2309.10968   2023年9月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.48550/arXiv.2309.10968

    researchmap

  • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems.

    Kei Kimura, Kazuhisa Makino

    CoRR   abs/2306.03368   2023年6月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.48550/arXiv.2306.03368

    researchmap

  • 整凸関数におけるL拡張可能性に関する一考察

    横山 健, 木村 慧, 横尾 真

    人工知能学会全国大会論文集   JSAI2023 ( 0 )   2J4GS102 - 2J4GS102   2023年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とし，その準備となる証明を行った．具体的には，まず，半整数格子点上で整凸関数と同様の性質を持つ関数，半整凸関数を新たに定義する．そして，整凸関数が半整凸関数に緩和できる条件や，半整凸関数がL凸性を満たす条件を調べる．さらに，これらを利用することで，整凸関数がL拡張可能である条件を明らかにするための方向性を示す．</p>

    DOI： 10.11517/pjsai.jsai2023.0_2j4gs102

    CiNii Research

  • 一次元区間上の施設配置メカニズムの戦略的操作の考察

    吉田 健人, 木村 慧, 横尾 真

    人工知能学会全国大会論文集   JSAI2023 ( 0 )   2F5GS502 - 2F5GS502   2023年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>一次元区間上の施設配置メカニズムの近似アルゴリズムによる解析において，エージェントの効用の最小値が大きいほどよいとされる平等性にもとづく目的関数や，エージェントの効用の総和が大きいほどよいとされる効率性にもとづいた目的関数が用いられた．目的関数に対する近似比は1に近いほどよいとされる．中点メカニズムは平等性に基づく目的関数で1の指標をもち，効率性に基づく目的関数でも比較的よい値をもつ．また，ナッシュメカニズムは平等性に基づく目的関数，効率性に基づく目的関数の双方で比較的1に近い値をもつ．しかし，中点メカニズムとナッシュメカニズムは戦略的操作が可能な場合が存在する． そこで，本研究では中点メカニズムとナッシュメカニズムに対してエージェントの申告値を考えることで，2種のメカニズムの戦略的操作の考察を行う． 結果として，中央値メカニズムはエージェントの申告値の区間が小さい場合にあるエージェントが効用を1にする戦略的操作が可能な場合が存在する．一方でナッシュメカニズムでは非常に多くのエージェントが特定の値を申告する場合に1人のエージェントの戦略的操作の影響が非常に小さくなることを示した．</p>

    DOI： 10.11517/pjsai.jsai2023.0_2f5gs502

    CiNii Research

  • ヘドニックゲームにおけるナッシュ安定性と情報拡散のインセンティブの両立性分析

    赤星 雄太, 木村 慧, 東藤 大樹, 横尾 真

    人工知能学会全国大会論文集   JSAI2023 ( 0 )   2F4GS503 - 2F4GS503   2023年   （ eISSN:27587347 ）

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>ヘドニックゲームは，エージェントのグループを適切なサブグループに分割する数理モデルで，従来協力ゲームの一分野として研究がなされてきた．一方，許可構造つきの協力ゲームは，エージェントのゲームへの参加が，別のエージェントによる許可制であるようなモデルである．本研究では，ヘドニックゲームに許可構造を導入し，情報拡散，すなわち，できる限り多くの許可を出すことのインセンティブが成立するヘドニックゲームの解について議論する．具体的には，まずナッシュ安定解と情報拡散が非両立であることを示す．この不可能性を受け，情報拡散のインセンティブを有するアルゴリズムを提案し，達成可能な社会的余剰の近似率を示す．</p>

    DOI： 10.11517/pjsai.jsai2023.0_2f4gs503

    CiNii Research

  • Algorithms for coloring reconfiguration under recolorability digraphs 査読

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira Suzuki

    Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022)   248   4:1 - 4:19   2022年12月   （ ISSN:18688969 ISBN:9783959772587 ）

    　詳細を見る

    記述言語：その他   出版者・発行元：Leibniz International Proceedings in Informatics, LIPIcs  

    In the k-Recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. This problem is known to be solvable in polynomial time if k ≤ 3, and is PSPACE-complete if k ≥ 4. In this paper, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph -→R, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of recolorability constraints -→R, showing that the problem is solvable in linear time when -→R is a directed cycle or is in a class of multitrees.

    DOI： 10.4230/LIPIcs.ISAAC.2022.4

    Scopus

    researchmap

  • Neighborhood Persistency of the Linear Optimization Relaxation of Integer Linear Optimization 査読

    312 - 323   2022年11月

    　詳細を見る

    記述言語：その他  

    DOI： 10.1007/978-3-031-18530-4_23

  • Quantaloidal approach to constraint satisfaction 査読

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura

    Proceedings of the 4th International Conference on Applied Category Theory (ACT 2021)   EPTCS 372   289 - 305   2022年10月

    　詳細を見る

    記述言語：その他  

    Quantaloidal approach to constraint satisfaction

  • Neighborhood persistency of the linear optimization relaxation of integer linear optimization

    Kei Kimura, Kotaro Nakayama

    CoRR   arXiv:2203.04557   312 - 323   2022年3月

    　詳細を見る

    記述言語：その他  

    DOI： 10.1007/978-3-031-18530-4_23

  • マルチエージェント経路探索のための厳密アルゴリズムの改良

    柴田 航志, 木村 慧, 東藤 大樹, 横尾 真

    人工知能学会全国大会論文集   JSAI2022 ( 0 )   1N1GS503 - 1N1GS503   2022年

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    <p>マルチエージェント経路探索 (Multi-agent Pathfinding, MAPF) 問題は，それぞれ相異なるスタートとゴールが定められたエージェントの集合を入力とし，エージェント同士の衝突が発生しない経路の割当を解とする問題である．NP困難であることが知られている，各エージェントがゴールに到達するまでに要する時間の総和の最小化について，Meta-Agent Conflict Based Search (MA-CBS) と呼ばれる有力な厳密アルゴリズムが存在する．MA-CBS の動作は，マージポリシーと呼ばれる条件に応じて変化するが，従来用いられてきた静的なマージポリシーのもとでは，一部のMAPFインスタンスにおいて膨大な実行時間を要することが知られている．そこで本論文では，アルゴリズムの性質を動的に変化させる新たなマージポリシーを提案する．また，提案したマージポリシーを実装したアルゴリズムが，従来と比較して多様なインスタンスで効率的に動作することを計算機実験で示す．</p>

    DOI： 10.11517/pjsai.jsai2022.0_1n1gs503

    CiNii Research

  • Neighborhood persistency of the linear optimization relaxation of integer linear optimization

    木村 慧

    arXiv   2203.04557   1 - 17   2022年

    　詳細を見る

  • Algorithms for coloring reconfiguration under recolorability digraphs 査読

    木村 慧

    Leibniz International Proceedings in Informatics   248   2022年

    　詳細を見る

  • Computational complexity of three-dimensional discrete tomography with missing data 査読

    Kei Kimura, Takuya Kamehashi

    Japan Journal of Industrial and Applied Mathematics   38 ( 3 )   823 - 858   2021年9月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s13160-021-00464-0

  • Quantaloidal approach to constraint satisfaction.

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura

    CoRR   abs/2107.01778   2021年7月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

  • Optimal Matroid Partitioning Problems 査読

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    Algorithmica   83 ( 6 )   1653 - 1676   2021年6月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s00453-021-00797-9

  • Trichotomy for the reconfiguration problem of integer linear systems. 査読

    Kei Kimura, Akira Suzuki

    Theor. Comput. Sci.   856   88 - 109   2021年2月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.tcs.2020.12.025

  • Stronger Hardness Results on the Computational Complexity of Picross 3D 査読

    Kei KIMURA

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E103.A ( 4 )   668 - 676   2020年4月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1587/transfun.2019eap1101

  • Trichotomy for the Reconfiguration Problem of Integer Linear Systems. 査読

    Kei Kimura, Akira Suzuki

    Proceedings of the 14th International Conference and Workshops on Algorithms and Computation, LNCS 12049   336 - 341   2020年3月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

    Trichotomy for the Reconfiguration Problem of Integer Linear Systems.
    In this paper, we consider the reconfiguration problem of integer linear<br />
    systems. In this problem, we are given an integer linear system &#36;I&#36; and two<br />
    feasible solutions &#36;oldsymbol{s}&#36; and &#36;oldsymbol{t}&#36; of &#36;I&#36;, and then asked<br />
    to transform &#36;oldsymbol{s}&#36; to &#36;oldsymbol{t}&#36; by changing a value of only<br />
    one variable at a time, while maintaining a feasible solution of &#36;I&#36;<br />
    throughout. &#36;Z(I)&#36; for &#36;I&#36; is the complexity index introduced by Kimura and<br />
    Makino (Discrete Applied Mathematics 200:67--78, 2016), which is defined by the<br />
    sign pattern of the input matrix. We analyze the complexity of the<br />
    reconfiguration problem of integer linear systems based on the complexity index<br />
    &#36;Z(I)&#36; of given &#36;I&#36;. We then show that the problem is (i) solvable in constant<br />
    time if &#36;Z(I)&#36; is less than one, (ii) weakly coNP-complete and<br />
    pseudo-polynomially solvable if &#36;Z(I)&#36; is exactly one, and (iii)<br />
    PSPACE-complete if &#36;Z(I)&#36; is greater than one. Since the complexity indices of<br />
    Horn and two-variable-par-inequality integer linear systems are at most one,<br />
    our results imply that the reconfiguration of these systems are in coNP and<br />
    pseudo-polynomially solvable. Moreover, this is the first result that reveals<br />
    coNP-completeness for a reconfiguration problem, to the best of our knowledge.

    DOI： 10.1007/978-3-030-39881-1_29

  • NP-Completeness of Fill-a-Pix and Sigma(P)(2)-Completeness of Its Fewest Clues Problem 査読

    Higuchi Yuta, Kimura Kei

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E102A ( 11 )   1490 - 1496   2019年11月

    　詳細を見る

    記述言語：その他  

    NP-Completeness of Fill-a-Pix and Sigma(P)(2)-Completeness of Its Fewest Clues Problem

    DOI： 10.1587/transfun.E102.A.1490

  • Trichotomy for the reconfiguration problem of integer linear systems.

    Kei Kimura, Akira Suzuki

    CoRR   abs/1911.02786   2019年11月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

  • Approximating Partially Bounded Degree Deletion on Directed Graphs 査読

    Toshihiro Fujito, Kei Kimura, Yuki Mizuno

    Journal of Graph Algorithms and Applications   23 ( 5 )   759 - 780   2019年10月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.7155/jgaa.00511

  • A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition. 査読

    Takuya Tamori, Kei Kimura

    WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings   209 - 218   2019年2月

    　詳細を見る

    記述言語：その他  

    A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition.

    DOI： 10.1007/978-3-030-10564-8_17

  • Linear Satisfiability Preserving Assignments (Extended Abstract).

    Kei Kimura, Kazuhisa Makino

    Proceedings of the 27th International Joint Conference on Artificial Intelligence   5622 - 5626   2018年7月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

    Linear Satisfiability Preserving Assignments (Extended Abstract).

    DOI： 10.24963/ijcai.2018/797

  • Maximum lifetime coverage problem with battery recovery effect 査読

    Norie Fu, Naonori Kakimura, Kei Kimura, Vorapong Suppakitpaisarn

    Sustainable Computing: Informatics and Systems   18   1 - 13   2018年6月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.suscom.2018.02.007

  • The Fewest Clues Problem of Picross 3D. 査読

    Kei Kimura, Takuya Kamehashi, Toshihiro Fujito

    9th International Conference on Fun with Algorithms, FUN 2018, June 13-15, 2018, La Maddalena, Italy   25:1-25:13   2018年6月

    　詳細を見る

    記述言語：その他  

    The Fewest Clues Problem of Picross 3D.

  • Approximating Partially Bounded Degree Deletion on Directed Graphs 査読

    Toshihiro Fujito, Kei Kimura, Yuki Mizuno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10755   32 - 43   2018年3月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.1007/978-3-319-75172-6_4

  • Autark assignments of Horn CNFs 査読

    Kei Kimura, Kazuhisa Makino

    Japan Journal of Industrial and Applied Mathematics   35 ( 1 )   297 - 309   2018年3月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s13160-017-0284-6

  • Linear Satisfiability Preserving Assignments 査読

    Kei Kimura, Kazuhisa Makino

    Journal of Artificial Intelligence Research   61   291 - 321   2018年2月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1613/jair.5658

    リポジトリ公開URL： https://hdl.handle.net/2324/7172672

  • Optimal matroid partitioning problems 査読

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    Leibniz International Proceedings in Informatics, LIPIcs   92   51:1-51:13   2017年12月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.4230/LIPIcs.ISAAC.2017.51

  • Optimal Matroid Partitioning Problems 査読

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    CoRR   abs/1710.00950   2017年10月

    　詳細を見る

    記述言語：その他  

    Optimal Matroid Partitioning Problems

  • Trichotomy for integer linear systems based on their sign patterns 査読

    Kei Kimura, Kazuhisa Makino

    DISCRETE APPLIED MATHEMATICS   200   67 - 78   2016年2月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.dam.2015.07.004

  • Maximum Lifetime Coverage Problems with Battery Recovery Effects 査読

    Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, Naonori Kakimura

    2014 IEEE GLOBAL COMMUNICATIONS CONFERENCE (GLOBECOM 2014)   118 - 124   2014年12月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.1109/GLOCOM.2014.7036794

  • Satisfiability Preserving Assignments and Their Local and Linear Forms

    Kei Kimura, Kazuhisa Makino

    MATHEMATICAL ENGINEERING TECHNICAL REPORTS   2014-34, University of Tokyo   2014年11月

    　詳細を見る

    記述言語：その他  

    Satisfiability Preserving Assignments and Their Local and Linear Forms

  • Trichotomy for Integer Linear Systems Based on Their Sign Patterns 査読

    Kei Kimura, Kazuhisa Makino

    29TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, (STACS 2012)   14   613 - 623   2012年3月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.4230/LIPIcs.STACS.2012.613

▼全件表示

講演・口頭発表等

  • 時間相関イメージセンサと多重極変調リング照明を用いた表面検査 (第25回センシングフォーラム資料--センシング技術の新たな展開と融合) -- (センサ(2))

    栗原 徹, 持田 康弘, 木村 慧

    センシングフォ-ラム資料  2008年9月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 整数線形システムの実行可能性問題に対する計算複雑さの指標

    木村慧

    木村慧, 牧野和久, 日本オペレーションズ・リサーチ学会「計算と最適化の新展開」研究部会（SCOPE@つくば）, 筑波大学  2011年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整数線形システムの実行可能性問題に対する計算複雑さの指標

    木村慧

    木村慧, 牧野和久, 日本オペレーションズ・リサーチ学会, 甲南大学  2011年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整数線形システムの実行可能性問題に対する計算複雑さの指標

    木村慧, 牧野和久

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集  2011年9月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 2-I-4 整数線形システムの実行可能性問題に対する計算複雑さの指標(離散最適化(3))

    木村 慧, 牧野 和久

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集  2011年9月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • Trichotomy for Integer Linear Systems Based on Their Sign Patterns

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 29th Symposium on Theoretical Aspects of Computer Science (STACS 2012), Paris, France  2012年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Trichotomy for Integer Linear Systems Based on Their Sign Patterns

  • 整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標

    木村慧

    木村慧, 牧野和久, 電子情報通信学会, 岐阜大学  2013年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標

    木村慧, 牧野和久

    電子情報通信学会大会講演論文集  2013年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • DS-1-6 整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標(DS-1.COMP学生シンポジウム,シンポジウムセッション)

    木村 慧, 牧野 和久

    電子情報通信学会総合大会講演論文集  2013年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2013), Veszprem, Hungary  2013年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

  • Maximum Lifetime Coverage Problems with Battery Recovery Effects

    V. Suppakitpaisarn

    F. Norie, V. Suppakitpaisarn, K. Kimura, N. Kakimura, Forum on Information Technology: Special Section on Advanced Topics on Basic Research, Tottori University (Poster Presentation)  2013年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧

    木村慧, 牧野和久, 日本オペレーションズ・リサーチ学会, 大阪大学  2014年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧

    木村慧, 牧野和久, 電子情報通信学会, 新潟大学  2014年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • A Complexity Index of Integer Linear Systems Based on Their Sign Patterns 招待 国際会議

    the 63th KPPY Combinatorics Workshop, Daegu, Korea  2014年3月 

    　詳細を見る

    記述言語：英語  

    国名：その他  

    A Complexity Index of Integer Linear Systems Based on Their Sign Patterns

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧, 牧野和久

    電子情報通信学会大会講演論文集(CD-ROM)  2014年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧, 牧野和久

    日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集  2014年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • DS-1-3 制約充足問題に対する線形固定可能割当ての解析(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

    木村 慧, 牧野 和久

    電子情報通信学会総合大会講演論文集  2014年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 1-G-6 制約充足問題に対する線形固定可能割当ての解析(離散最適化(1))

    木村 慧, 牧野 和久

    日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集  2014年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧

    木村慧, 牧野和久, 日本オペレーションズ・リサーチ学会「最適化の理論と応用」研究部会SOTA, 筑波大学  2014年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Maximum Lifetime Coverage Problems with Battery Recovery Effects

    Vorapong Suppakitpaisarn

    Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, and Naonori Kakimura, IEEE Global Communications Conference (GLOBECOM 2014), Austin, TX, USA  2014年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Maximum Lifetime Coverage Problems with Battery Recovery Effects

  • A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, ISAAC2015 preworkshop: ELC Workshop on Algorithms and Computation, Kyoto, Japan  2015年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

  • 整数線形不等式系の実行可能性問題における多項式時間可解部分クラス 招待

    木村慧

    2017年電子情報通信学会総合大会 COMP-ELC学生シンポジウム, 名城大学  2017年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整数線形不等式系の実行可能性問題における多項式時間可解部分クラス

    木村慧

    電子情報通信学会大会講演論文集(CD-ROM)  2017年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • Min-sum-max matroid partitioning problem

    Hanna Sumita

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita, The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2017), Budapest, Hungary  2017年5月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Min-sum-max matroid partitioning problem

  • Optimal Matroid Partitioning Problems

    Kei Kimura

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita, The 28th International Symposium on Algorithms and Computation (ISAAC 2017), Phuket, Thailand  2017年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Optimal Matroid Partitioning Problems

  • ペンシルパズル「Fill-a-Pix」のNP完全性

    樋口雄太

    樋口雄太, 木村慧, 組合せゲーム・パズル(CGP)プロジェクト 第13回研究集会, 大阪府立大学  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • ぷよを自由に配置できる場合のぷよぷよの連鎖数判定問題

    澁谷諒祐

    澁谷諒祐, 木村慧, 組合せゲーム・パズル(CGP)プロジェクト 第13回研究集会, 大阪府立大学  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Approximating Partially Bounded Degree Deletion on Directed Graphs

    Kei Kimura

    Toshihiro Fujito, Kei Kimura, and Yuki Mizuno, The 12th International Conference and Workshops on Algorithms and Computation (WALCOM 2018), Dhaka, Bangladesh  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Approximating Partially Bounded Degree Deletion on Directed Graphs

  • ペンシルパズル「Fill-a-Pix」のNP完全性

    樋口雄太, 木村慧

    組合せゲーム・パズル(CGP)プロジェクト 第13回研究集会  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：日本国  

  • ぷよを自由に配置できる場合のぷよぷよの連鎖数判定問題

    澁谷諒祐, 木村慧

    組合せゲーム・パズル(CGP)プロジェクト 第13回研究集会  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：日本国  

  • The Fewest Clues Problem of Picross 3D

    Kei Kimura

    Kei Kimura, Takuya Kamehashi, and Toshihiro Fujito, The 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy  2018年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    The Fewest Clues Problem of Picross 3D

  • Linear Satisfiability Preserving Assignments (Extended Abstract)

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), Stockholm, Seweden  2018年7月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Linear Satisfiability Preserving Assignments (Extended Abstract)

  • A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition

    Takuya Tamori

    Takuya Tamori and Kei Kimura, The 13th International Conference and Workshops on Algorithms and Computation (WALCOM 2019), Guwahati, India  2019年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition

  • Three-dimensional discrete tomography with restriction on height and constraint numbers

    Kei Kimura

    Takuya Kamehashi and Kei Kimura, The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2019), Tokyo, Japan  2019年5月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Three-dimensional discrete tomography with restriction on height and constraint numbers

  • Computational complexity of the reconfiguration problem of integer linear systems

    2020年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Computational complexity of the reconfiguration problem of integer linear systems

  • 整数計画における遷移問題の計算量

    木村慧

    木村慧, 鈴木顕, 日本応用数理学会 第16回研究部会連合発表会, 中央大学  2020年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 制約充足問題に対する充足可能性保存割当ての解析 招待

    木村慧

    人工知能学会 第112回人工知能基本問題研究会(SIG-FPAI), 柳川市藤吉コミュニティセンター  2020年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Trichotomy for the reconfiguration problem of integer linear systems

    Kei Kimura

    Kei Kimura and Akira Suzuki, The 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Singapore, Singapore  2020年4月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Trichotomy for the reconfiguration problem of integer linear systems

  • 整数計画における遷移問題の計算量

    木村慧

    木村慧, 鈴木顕, 日本応用数理学会 2020年度 年会, オンライン開催  2020年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 制約充足問題に対する充足可能性保存割当ての解析 招待

    木村慧

    人工知能学会 第113回人工知能基本問題研究会(SIG-FPAI), オンライン開催  2020年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Quantaloidal approach to constraint satisfaction

    Soichiro Fujii

    Soichiro Fujii, Yuni Iwamasa, and Kei Kimura, The 4th International Conference on Applied Category Theory, online  2021年7月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Quantaloidal approach to constraint satisfaction

  • マルチエージェント経路探索アルゴリズムの改良のための一検討

    柴田航志

    柴田航志，木村慧，東藤大樹，横尾真, SMASH(Symposium on Multi Agent Systems for Harmonization)22 Winter Symposium, オンライン  2022年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 多項式時間可解なHorn ILS及びTVPI ILSにおける遷移問題の拡張に関する研究

    重信 賢直

    重信 賢直, 神⼭ 直之, ⽊村 慧, 科研費・学術変⾰領域研究(B)「組合せ遷移の展開に向けた計算機科学・⼯学・数学によるアプローチの融合」, 組合せ遷移の学⽣シンポジウム, オンライン  2022年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • ぷよを自由に配置できるぷよぷよの連鎖数判定問題: 色数制限を課した場合

    澁谷諒祐

    澁谷諒祐, 木村慧, 組合せゲーム・パズル(CGP)プロジェクト 第16回研究集会, オンライン  2022年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Neighborhood persistency of the linear optimization relaxation of integer linear optimization

    Kei Kimura

    Kei Kimura and Kotaro Nakayama, The 7th International Symposium on Combinatorial Optimization (ISCO), online  2022年5月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Neighborhood persistency of the linear optimization relaxation of integer linear optimization

  • 整数最適化の線形緩和における近傍永続性

    木村慧

    木村慧, 中山鼓太郎, 日本応用数理学会 2022年度 年会, オンライン開催  2022年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 遷移可能性制約をもつ彩色遷移問題 招待

    木村慧

    学術変革(B)「組合せ遷移」セミナー・勉強会  2022年10月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 一次元線分上の施設配置メカニズムの戦略的操作不可能性の緩和

    吉田健人

    吉田健人, 木村慧, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2023 WINTER SYMPOSIUM, 名古屋工業大学 + オンライン  2023年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整凸関数におけるL拡張可能性

    横山健

    横山健，木村慧，横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2023 WINTER SYMPOSIUM, 名古屋工業大学 + オンライン  2023年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Algorithms for coloring reconfiguration under recolorability digraphs

    Yuni Iwamasa

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki, The 33rd International Symposium on Algorithms and Computation (ISAAC), Seoul, Korea  2022年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Algorithms for coloring reconfiguration under recolorability digraphs

  • マルチエージェント経路探索のための厳密アルゴリズムの改良

    柴田 航志

    柴田 航志, 木村 慧, 東藤 大樹, 横尾 真, 人工知能学会全国大会, 京都国際会館＋オンライン  2022年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 2期間マッチングにおける公平性と非浪費性

    米谷颯人

    米谷颯人, 木村慧, 孫兆鴻, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • ソーシャルネットワーク上での両方向マッチングにおける公平性の緩和

    竹島遼太

    竹島遼太, 木村慧, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 両方向マッチングにおける公平性の新たな緩和

    若杉天真

    若杉天真, 木村慧, 孫兆鴻, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整凸関数の線形補間による L 拡張可能性に関する一考察

    横山 健

    横山健, 岩政勇仁, 木村慧 横尾真, 日本応用数理学会第20回研究部会連合発表会, 長岡技術科学大学  2024年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 34th International Symposium on Algorithms and Computation (ISAAC), Kyoto, Japan  2023年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems

  • ヘドニックゲームにおけるナッシュ安定性と情報拡散のインセンティブの両立性分析

    赤星 雄太

    赤星 雄太, 木村 慧, 東藤 大樹, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 一次元区間上の施設配置メカニズムの戦略的操作の考察

    吉田 健人

    吉田 健人, 木村 慧, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整凸関数におけるL拡張可能性に関する一考察

    横山 健

    横山 健, 木村 慧, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 遷移可能性制約をもつ彩色遷移問題 招待

    木村慧

    学術変革(B)「組合せ遷移」セミナー・勉強会  2022年10月 

    　詳細を見る

  • 整数最適化の線形緩和における近傍永続性

    木村慧

    木村慧, 中山鼓太郎, 日本応用数理学会 2022年度 年会, オンライン開催  2022年9月 

    　詳細を見る

  • 整凸関数の線形補間による L 拡張可能性に関する一考察

    横山 健

    横山健, 岩政勇仁, 木村慧 横尾真, 日本応用数理学会第20回研究部会連合発表会, 長岡技術科学大学  2024年3月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • 整凸関数におけるL拡張可能性に関する一考察

    横山 健

    横山 健, 木村 慧, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • 整凸関数におけるL拡張可能性

    横山健

    横山健，木村慧，横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2023 WINTER SYMPOSIUM, 名古屋工業大学 + オンライン  2023年2月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • 多項式時間可解なHorn ILS及びTVPI ILSにおける遷移問題の拡張に関する研究

    重信 賢直

    重信 賢直, 神⼭ 直之, ⽊村 慧, 科研費・学術変⾰領域研究(B)「組合せ遷移の展開に向けた計算機科学・⼯学・数学によるアプローチの融合」, 組合せ遷移の学⽣シンポジウム, オンライン  2022年3月 

    　詳細を見る

  • 両方向マッチングにおける公平性の新たな緩和

    若杉天真

    若杉天真, 木村慧, 孫兆鴻, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年2月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • 一次元線分上の施設配置メカニズムの戦略的操作不可能性の緩和

    吉田健人

    吉田健人, 木村慧, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2023 WINTER SYMPOSIUM, 名古屋工業大学 + オンライン  2023年2月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • 一次元区間上の施設配置メカニズムの戦略的操作の考察

    吉田 健人

    吉田 健人, 木村 慧, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • マルチエージェント経路探索アルゴリズムの改良のための一検討

    柴田航志

    柴田航志，木村慧，東藤大樹，横尾真, SMASH(Symposium on Multi Agent Systems for Harmonization)22 Winter Symposium, オンライン  2022年2月 

    　詳細を見る

  • マルチエージェント経路探索のための厳密アルゴリズムの改良

    柴田 航志

    柴田 航志, 木村 慧, 東藤 大樹, 横尾 真, 人工知能学会全国大会, 京都国際会館＋オンライン  2022年6月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • ヘドニックゲームにおけるナッシュ安定性と情報拡散のインセンティブの両立性分析

    赤星 雄太

    赤星 雄太, 木村 慧, 東藤 大樹, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • ソーシャルネットワーク上での両方向マッチングにおける公平性の緩和

    竹島遼太

    竹島遼太, 木村慧, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年3月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • ぷよを自由に配置できるぷよぷよの連鎖数判定問題: 色数制限を課した場合

    澁谷諒祐

    澁谷諒祐, 木村慧, 組合せゲーム・パズル(CGP)プロジェクト 第16回研究集会, オンライン  2022年3月 

    　詳細を見る

  • Neighborhood persistency of the linear optimization relaxation of integer linear optimization

    Kei Kimura

    Kei Kimura and Kotaro Nakayama, The 7th International Symposium on Combinatorial Optimization (ISCO), online  2022年5月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • Algorithms for coloring reconfiguration under recolorability digraphs

    Yuni Iwamasa

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki, The 33rd International Symposium on Algorithms and Computation (ISAAC), Seoul, Korea  2022年12月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 34th International Symposium on Algorithms and Computation (ISAAC), Kyoto, Japan  2023年12月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

  • 2期間マッチングにおける公平性と非浪費性

    米谷颯人

    米谷颯人, 木村慧, 孫兆鴻, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年3月 

    　詳細を見る

    会議種別：口頭発表（一般）  

    researchmap

▼全件表示

MISC

  • Optimal Matroid Partitioning Problems 査読

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    CoRR   2017年10月

    　詳細を見る

    記述言語：その他  

    Optimal Matroid Partitioning Problems

  • 制約充足問題に対する充足可能性保存割当ての解析とそのアルゴリズム設計への応用

    木村慧

    博士論文, 東京大学, 情報理工学系研究科   2015年3月

    　詳細を見る

    記述言語：その他  

  • q-Horn システムに対する組合せ的アルゴリズム

    木村慧

    修士論文, 東京大学, 情報理工学系研究科   2011年3月

    　詳細を見る

    記述言語：その他  

  • 行列の同時ブロック対角化：複素数上の分解と実数上の分解

    木村慧

    卒業論文, 東京大学, 工学部   2009年3月

    　詳細を見る

    記述言語：その他  

所属学協会

  • 電子情報通信学会

    2014年1月 - 現在

    　 詳細を見る

  • 日本オペレーションズ・リサーチ学会

    2011年4月 - 現在

    　 詳細を見る

  • 日本オペレーションズ・リサーチ学会

  • 電子情報通信学会

委員歴

  • 日本オペレーションズ・リサーチ学会   九州支部幹事  

    2024年4月 - 2026年3月   

    　 詳細を見る

  • 電子情報通信学会コンピュテーション研究会   専門委員  

    2021年6月 - 2023年6月   

    　 詳細を見る

  • 電子情報通信学会   英文論文誌小特集編集委員会 編集委員  

    2019年7月 - 2023年9月   

    　 詳細を見る

    団体区分：学協会

    researchmap

  • The 2017 International Conference on Advanced Informatics: Concept Theory and Applications (ICAICTA)   Program Commitee  

    　 詳細を見る

  • The 23rd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-24)   Program Committee  

    　 詳細を見る

  • Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)   Program Committee  

    　 詳細を見る

  • The 11th International Conference on Fun with Algorithms (FUN 2022)   Program Commitee  

    　 詳細を見る

  • The 6th International Congress on Advanced Applied Informatics (AAI 2017)   Program Commitee  

    　 詳細を見る

▼全件表示

学術貢献活動

  • RIMS 共同研究「組合せ最適化セミナー」

    2016-2019年 幹事, 2020-2023年 研究提案者 

    　詳細を見る

共同研究・競争的資金等の研究課題

  • 制約充足問題の遷移問題に対する普遍代数学を用いたアプローチ

    研究課題/領域番号：21K17700  2021年 - 2025年

    日本学術振興会  科学研究費助成事業  若手研究

    木村 慧

    　 詳細を見る

    資金種別：科研費

    遷移問題とは，ある問題の２つの解が与えられたときに，片方の解からもう片方の解へと段階的に遷移することが可能であるか否かを判定する問題である．この問題は，従来考えられて来た解の探索問題や最適化問題と異なり，既に構築し運用されているシステムを，運用を止めずに再構築する際に有用であると考えられている．本研究では，制約充足問題という様々な問題を定式化することのできる問題の遷移問題に対し，普遍代数学を用いた計算複雑さの系統的な分類を行う．

    CiNii Research

  • 演算不変性を用いた整数計画問題のアルゴリズム開発

    2020年 - 2022年

    戦略的創造研究推進事業 (文部科学省)

    　 詳細を見る

    担当区分：研究代表者  資金種別：受託研究

  • 局所構造を利用した高速なアルゴリズムの開発

    研究課題/領域番号：19K22841  2019年 - 2023年

    日本学術振興会  科学研究費助成事業  挑戦的研究（萌芽）

    牧野 和久, 木村 慧

    　 詳細を見る

    担当区分：研究分担者  資金種別：科研費

    本研究では，局所的な離散構造を利用することで，効率的なアルゴリズム設計のための基 礎理論の構築を目指す．具体的には，離散的な構造解析手法に基づく，（１）局所解改善 の方法論，（２）局所解の列挙手法の研究を行う．離散アルゴリズムは情報化社会におい て極めて重要であるが，その計算量的な難しさから，メタ戦略など品質保証されない手法 を用いて解かれることが多い．これらの手法の多くは局所探索法を発展させたものであり ，局所解の離散構造の解析は非常に意義深く，チャレンジングな研究課題である．

    CiNii Research

  • The 14th International Conference and Workshop on Algorithms and Computation に参加し論文発表を行う

    2019年

    海外渡航旅費援助

    　 詳細を見る

    担当区分：研究代表者  資金種別：受託研究

  • The 27th International Joint Conference on Arti cial Intelligence に参加し論文発表を行う

    2018年

    研究者海外派遣助成

    　 詳細を見る

    担当区分：研究代表者  資金種別：受託研究

  • 整数計画問題に対するアルゴリズム開発

    2018年

    平成３０年度教育研究活性化経費（若手研究）

    　 詳細を見る

    担当区分：研究代表者  資金種別：学内資金・基金等

  • 離散構造をもつ判定問題への連続最適化手法の構築

    研究課題/領域番号：15H06286  2015年 - 2016年

    日本学術振興会  科学研究費助成事業  研究活動スタート支援

    　 詳細を見る

    資金種別：科研費

  • 制約充足問題に対する数理計画法を用いたアプローチ

    2013年 - 2014年

    日本学術振興会  特別研究員

    　 詳細を見る

    資金種別：共同研究

▼全件表示

担当授業科目

  • データ構造とアルゴリズムⅣ

    2024年6月 - 2024年8月   夏学期

  • データ構造とアルゴリズムⅡＢ

    2024年6月 - 2024年8月   夏学期

  • 【通年】情報理工学研究Ⅰ

    2024年4月 - 2025年3月   通年

  • 【通年】情報理工学講究

    2024年4月 - 2025年3月   通年

  • 【通年】情報理工学演習

    2024年4月 - 2025年3月   通年

  • 情報理工学読解

    2024年4月 - 2024年9月   前期

  • 情報理工学論議Ⅰ

    2024年4月 - 2024年9月   前期

  • 情報理工学論述Ⅰ

    2024年4月 - 2024年9月   前期

  • データ構造とアルゴリズムⅢ

    2024年4月 - 2024年6月   春学期

  • データ構造とアルゴリズムⅡＡ

    2024年4月 - 2024年6月   春学期

  • Evidence-based Policy Making II

    2023年12月 - 2024年2月   冬学期

  • データに基づく政策決定特論Ⅱ

    2023年12月 - 2024年2月   冬学期

  • (IUPE)Data Structure and Algorithms IB

    2023年12月 - 2024年2月   冬学期

  • 情報理工学論議Ⅱ

    2023年10月 - 2024年3月   後期

  • 情報理工学論述Ⅱ

    2023年10月 - 2024年3月   後期

  • 情報理工学演示

    2023年10月 - 2024年3月   後期

  • Evidence-based Policy Making I

    2023年10月 - 2023年12月   秋学期

  • データに基づく政策決定特論Ⅰ

    2023年10月 - 2023年12月   秋学期

  • (IUPE)Data Structure and Algorithms IA

    2023年10月 - 2023年12月   秋学期

  • 【通年】情報理工学研究Ⅰ

    2023年4月 - 2024年3月   通年

  • 数学創発モデリング

    2023年4月 - 2024年3月   通年

  • 【通年】情報理工学講究

    2023年4月 - 2024年3月   通年

  • 【通年】情報理工学演習

    2023年4月 - 2024年3月   通年

  • 情報理工学読解

    2023年4月 - 2023年9月   前期

  • 情報理工学論議Ⅰ

    2023年4月 - 2023年9月   前期

  • 情報理工学論述Ⅰ

    2023年4月 - 2023年9月   前期

  • (IUPE)Data Structure and Algorithms IB

    2022年12月 - 2023年2月   冬学期

  • データに基づく政策決定特論Ⅱ

    2022年12月 - 2023年2月   冬学期

  • 電気情報工学実験II,III(2022後期)

    2022年10月 - 2023年3月   後期

  • 物理学入門IIB(2022後期オムニバス)

    2022年10月 - 2023年3月   後期

  • プログラミング技法

    2022年10月 - 2023年3月   後期

  • プログラミング技法

    2022年10月 - 2023年3月   後期

  • 情報理工学論議Ⅱ

    2022年10月 - 2023年3月   後期

  • 情報理工学論述Ⅱ

    2022年10月 - 2023年3月   後期

  • 情報理工学演示

    2022年10月 - 2023年3月   後期

  • (IUPE)Data Structure and Algorithms IA

    2022年10月 - 2022年12月   秋学期

  • データに基づく政策決定特論Ⅰ

    2022年10月 - 2022年12月   秋学期

  • 情報理工学講究

    2022年4月 - 2023年3月   通年

  • 数学共創モデリング

    2022年4月 - 2023年3月   通年

  • 情報理工学演習

    2022年4月 - 2023年3月   通年

  • 情報理工学研究Ⅰ

    2022年4月 - 2023年3月   通年

  • 情報理工学論述Ⅰ

    2022年4月 - 2022年9月   前期

  • 情報理工学読解

    2022年4月 - 2022年9月   前期

  • Data Structure and Algorithms IA,IB

    2022年4月 - 2022年9月   前期

  • データに基づく政策決定特論I,II

    2022年4月 - 2022年9月   前期

  • 数学共創概論I

    2022年4月 - 2022年9月   前期

  • 情報理工学論議Ⅰ

    2022年4月 - 2022年9月   前期

  • 電気情報工学実験II,III

    2021年10月 - 2022年3月   後期

  • 国際科学特論II(2021後期オムニバス)

    2021年10月 - 2022年3月   後期

  • 国際科学特論Ⅱ

    2021年10月 - 2021年12月   秋学期

▼全件表示

FD参加状況

  • 2023年3月   役割：参加   名称：【シス情FD】独・蘭・台湾での産学連携を垣間見る-Industy 4.0・量子コンピューティング・先端半導体-

    主催組織：部局

  • 2023年1月   役割：参加   名称：【シス情FD】若手教員による研究紹介⑦

    主催組織：部局

  • 2022年10月   役割：参加   名称：【シス情FD】若手教員による研究紹介⑥

    主催組織：部局

  • 2022年9月   役割：参加   名称：【シス情FD】研究機器の共用に向けて

    主催組織：部局

  • 2022年7月   役割：参加   名称：【シス情FD】若手教員による研究紹介⑤

    主催組織：部局

  • 2022年6月   役割：参加   名称：【シス情FD】電子ジャーナル等の今後について

    主催組織：部局

  • 2022年5月   役割：参加   名称：【シス情FD】若手教員による研究紹介④「量子コンピュータ・システム・アーキテクチャの研究～道具になることを目指して～」

    主催組織：部局

  • 2022年4月   役割：参加   名称：【シス情FD】第4期中期目標・中期計画等について

    主催組織：部局

  • 2022年4月   役割：参加   名称：令和４年度 第１回全学ＦＤ（新任教員の研修）The 1st All-University FD (training for new faculty members) in FY2022

    主催組織：全学

  • 2022年3月   役割：参加   名称：全学FD:メンタルヘルス講演会

    主催組織：全学

  • 2022年1月   役割：参加   名称：【シス情FD】シス情関連の科学技術に対する国の政策動向（に関する私見）

    主催組織：部局

  • 2021年12月   役割：参加   名称：【シス情FD】企業出身教員から見た大学

    主催組織：部局

  • 2021年11月   役割：参加   名称：【シス情FD】若手教員による研究紹介　及び　研究費獲得のポイント等について③

    主催組織：部局

  • 2021年10月   役割：参加   名称：【シス情FD】熊本高専と九大システム情報との交流・連携に向けて ー 3年半で感じた高専の実像 ー

    主催組織：部局

▼全件表示

その他教育活動及び特記事項

  • 2023年  クラス担任  学部

  • 2022年  クラス担任  学部

社会貢献活動

  • 人工知能によるスケジュール作成を学ぼう

    埼玉大学  2021年8月

    　詳細を見る

    対象： 幼稚園以下,　小学生,　中学生,　高校生

  • 整数計画法によるパズル解法

    2018年

    　詳細を見る

    整数計画法によるパズル解法

  • 整数計画法によるパズル解法

    2017年

    　詳細を見る

    整数計画法によるパズル解法

  • 整数計画法によるパズル解法

    2016年

    　詳細を見る

    整数計画法によるパズル解法

メディア報道

  • 計算機（コンピュータ）により解ける問題、解けない問題

    FMラジオ広報「天伯之城 ギカダイ」  2018年2月

    　詳細を見る

    計算機（コンピュータ）により解ける問題、解けない問題

政策形成、学術振興等への寄与活動

  • 2021年6月 - 2023年6月   電子情報通信学会コンピュテーション研究会

    専門委員

  • 2019年7月 - 2023年9月   電子情報通信学会

    英文論文誌小特集編集委員会 編集委員

  • 2018年8月 - 2019年9月   電子情報通信学会

    英文論文誌小特集編集委員会 編集委員

  • 2017年5月 - 2021年5月   電子情報通信学会

    Associate Editor of IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  • 2017年5月 - 2021年5月   電子情報通信学会

    基礎・境界ソサイエティ和文論文誌編集委員

  • 2016年5月 - 2018年5月   日本オペレーションズ・リサーチ学会

    論文誌編集幹事

  •   The 11th International Conference on Fun with Algorithms (FUN 2022)

    Program Commitee

  •   2016, 2017, 2018, 2019年 幹事, 2020年 研究提案者

    RIMS 共同研究「組合せ最適化セミナー」

  •   The 2017 International Conference on Advanced Informatics: Concept Theory and Applications (ICAICTA)

    Program Commitee

  •   The 6th International Congress on Advanced Applied Informatics (AAI 2017)

    Program Commitee

▼全件表示

学内運営に関わる各種委員・役職等

  • 2024年4月 - 2026年3月   その他 九州支部幹事

  • 2023年4月 - 2024年3月   部門 安全衛生委員

  • 2022年4月 - 2023年3月   部門 情報通信委員

  • その他 Program Committee

  • その他 Program Committee