Updated on 2024/09/27

Information

 

写真a

 
KIMURA KEI
 
Organization
Faculty of Information Science and Electrical Engineering Department of Informatics Associate Professor
School of Engineering Department of Electrical Engineering and Computer Science（Concurrent）
Graduate School of Information Science and Electrical Engineering Department of Information Science and Technology（Concurrent）
Joint Graduate School of Mathematics for Innovation （Concurrent）
Title
Associate Professor
Profile
広くは計算機科学，数理工学，応用数学，より詳細には組合せ最適化，離散アルゴリズムの研究に従事
External link

Degree

  • Doctor of Information Science and Technology

Research History

  • Kyushu University Associate Professor

    2021.10 - Present

    　 More details

Research Interests・Research Keywords

  • Research theme：Combinatorial Optimization

    Keyword：Combinatorial Optimization

    Research period： 2024

  • Research theme：Integer Programming

    Keyword：Integer Programming

    Research period： 2024

  • Research theme：Constraint Satisfaction Problem

    Keyword：Constraint Satisfaction Problem

    Research period： 2024

  • Research theme：Algorithm

    Keyword：Algorithm

    Research period： 2024

  • Research theme：Mathematical Optimization, Algorithms, Mechanism Design, Theoretical Comupter Science

    Keyword：Integer Linear Optimization, Discrete Structures, Matching, Computational Complexity

    Research period： 2022.6

Awards

  • 準優秀賞

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

  • 準優秀賞

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

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

    　More details

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

    2021.11   埼玉大学 工学部  

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

    2020.12   埼玉大学 工学部  

  • 系長賞

    2018.11   豊橋技術科学大学 情報・知能工学系  

  • 最優秀論文賞

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

  • 最優秀発表賞受賞

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

▼display all

Papers

  • 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

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    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

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.48550/arXiv.2401.06405

    researchmap

  • Non-Obvious Manipulability in Ordered Weighted Average Mechanisms for Facility Location Games

    YOSHIDA Kento, KIMURA Kei, TODO Taiki, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2024 ( 0 )   2F6GS502 - 2F6GS502   2024   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>In this presentation, we consider a facility location game on a one-dimensional line segment, i.e., a problem in which participating agents declare their positions on a one-dimensional line segment and a mechanism determines the placement of facilities based on these declarations. In particular, we focus on the ordered weighted average (OWA) mechanisms and discuss its non-obvious manipulability. An OWA mechanism is a mechanism that orders the agent's reported values in ascending order, applies weights according to that order, and returns the sum of the weights. In this presentation, we analyze how the non-obvious manipulability changes by changing the weights in an OWA.</p>

    DOI： 10.11517/pjsai.jsai2024.0_2f6gs502

    CiNii Research

  • A study on L-extendability of integrally convex functions by linear interpolation

    YOKOYAMA Ken, IWAMASA Yuni, KIMURA Kei, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2024 ( 0 )   3Xin235 - 3Xin235   2024   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>Integrally convex functions are a basic class of functions in discrete convex analysis, including M-convex functions and L-convex functions. Recently, the concept of L-extendable functions has been proposed for algorithm development for discrete optimization problems. A function h on an integer lattice is L-extendable if there exists an L-convex function g on a half-integer lattice such that the restriction of g on the integer lattice coincides with that of h. L-extendability is known to be useful in developing approximation algorithms and fast exact algorithms for various discrete optimization problems that are NP-hard. The purpose of this paper is to investigate L-extendability of integrally convex functions. In particular, we focus on L-extensibility by linear interpolation and discuss a characterization of integrally convex functions for which such extensions are possible.</p>

    DOI： 10.11517/pjsai.jsai2024.0_3xin235

    CiNii Research

  • Various Anonymity Properties in Diffusion Mechanism Design for Facility Location Games

    ANDO Ryoto, KIMURA Kei, TODO Taiki, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2024 ( 0 )   3Xin250 - 3Xin250   2024   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>Diffusion mechanism design is a new research paradigm in the literature of mechanism design, which aims to incentivise agents to invite as many colleagues as possible to participate in a mechanism. An existing work on diffusion mechanism design for facility location games showed that there is no mechanism that satisfies strategy-proofness, Pareto efficiency and full anonymity, as well as proposed two naive mechanisms that satisfy strategy-proofness and Pareto efficiency by ignoring the full anonymity property. In this paper we aim to reveal to what extent strategy-proof and Pareto efficient mechanisms could be anonymous. We first define a class of anonymity properties by introducing a concept of partitions of the set of participating agents, and clarify a sufficient condition on partitions that guarantees the existence of mechanisms satisfying an anonymity property, as well as strategy-proofness and Pareto efficiency.</p>

    DOI： 10.11517/pjsai.jsai2024.0_3xin250

    CiNii Research

  • New Concept of Fairness Applicable to School Choice

    WAKASUGI Temma, KIMURA Kei, SUN Zhaohong, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2024 ( 0 )   2F6GS501 - 2F6GS501   2024   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>The theory of two-sided matching has been extensively developed, and it is hoped that matching will reduce students' envies and improve overall welfare. However, it turns out that there exists a trade-off between efficiency and fairness. Therefore, keeping fairness at a certain level that can be applied in the real world also leads to increased efficiency. Our contribution is to establish a weaker fairness requirement called reverse Envy-Freeness from up to k peers (r-EF-k). r-EF-k requires that each student is envied by at most k students. By varying k, r-EF-k can represent different levels of fairness. We discuss mechanism that satisfy r-EF-k and certain efficiency properties.</p>

    DOI： 10.11517/pjsai.jsai2024.0_2f6gs501

    CiNii Research

  • Local envy freeness in two-sided matching

    TAKESHIMA Ryota, KIMURA Kei, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2024 ( 0 )   3Xin2112 - 3Xin2112   2024   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>According to the insights of behavioral economics, it is believed that people feel happiness by comparing themselves with others who are close to them. In accordance with this insight, this study considers two-sided matching where envy occurs only with those directly connected in the social network, and examines the relationship between efficiency and fairness. In particular, we define the aforementioned envy as local envy, and adopt the absence of local envy as a relaxation of conventional fairness. Then, by restricting preferences on one side, we discuss the existence of matchings that are both locally envy free and Pareto efficient, as well as mechanisms to find such matchings.</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 ）

    　More details

    Publisher：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

  • Fairness and Nonwastefulness in Two-Period Matching

    KOMETANI Hayato, KIMURA Kei, SUN Zhaohong, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2024 ( 0 )   1I3GS501 - 1I3GS501   2024   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>In this paper, we explore a two-period matching problem in which agents' preferences may evolve over time. This model enables agents to be matched with different partners over the two periods. Previous research defines dynamic stability as the absence of any single agent or pair of agents gaining an advantage through coalition across any period. We introduce new fairness, nonwastefulness and individually rationality notions tailored for the two-period matching setting and examine its relationship with dynamic stability. We also discuss the existence of matching that simultaneously satisfies the newly introduced fairness and nonwastefulness properties.</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

    　More details

    Language：Others   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.ISAAC.2023.47

    researchmap

    Other Link： 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

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    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

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.48550/arXiv.2306.03368

    researchmap

  • A study on L-extendability of integrally convex functions

    YOKOYAMA Ken, KIMURA Kei, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2023 ( 0 )   2J4GS102 - 2J4GS102   2023   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>Integrally convex functions are a basic class of functions in discrete convex analysis, including M-convex functions and L-convex functions. Recently, the concept of L-extendable functions has been proposed for algorithm development for discrete optimization problems. A function h on an integer lattice is L-extendable if there exists an L-convex function g on a half-integer lattice such that the restriction of g on the integer lattice coincides with that of h. L-extendability is known to be useful in developing approximation algorithms and fast exact algorithms for various discrete optimization problems that are NP-hard. The purpose of this paper is to investigate L-extendability of integrally convex functions. Specifically, we first define a half-integrally convex function on a half-integer lattice that has properties similar to those of an integrally convex function. Then, we investigate the conditions under which an integrally convex function can be relaxed to a half-integrally convex function. Finally, we point out a research direction to investigate the condition under which an integrally convex function is L-extendable.</p>

    DOI： 10.11517/pjsai.jsai2023.0_2j4gs102

    CiNii Research

  • Analysis of manipulation on mechanisms for a one-dimensional facility location problem

    YOSHIDA Kento, KIMURA Kei, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2023 ( 0 )   2F5GS502 - 2F5GS502   2023   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>We consider manipulation on facility location mechanisms which do not satisfy strategyproofness.Specifically, we deal with two mechanisms called the midpoint mechanism and the Nash mechanism. In the midpoint mechanism, the location is determined as half of the sum of the minimum and maximum values among the reported values.In the Nash mechanism, the location of facility is determined as that maximizing the product of utilities of the agents.Agents can improve their utility by manipulation in those mechanisms. In this paper, we investigate how one agent can manipulate the location of a facility in those mechanisms.</p>

    DOI： 10.11517/pjsai.jsai2023.0_2f5gs502

    CiNii Research

  • Analysing the compatibility of Nash stability and information diffusion in hedonic games

    AKAHOSHI Yuta, KIMURA Kei, TODO Taiki, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2023 ( 0 )   2F4GS503 - 2F4GS503   2023   （ eISSN:27587347 ）

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>Hedonic games are mathematical models in which a group of agents is divided into appropriate subgroups, and have been studied as a field of cooperative games. Cooperative games with permission structures, on the other hand, are models in which an agent’s participation in a game is by permission of another agent. In this paper, we introduce a permission structure into SASHG, a type of hedonic game, and consider solutions to hedonic games in which information diffusion, i.e., the incentive to issue as many permissions as possible, holds. Specifically, we first show that Nash stable solutions and information diffusion are incompatible. Given this impossibility, we propose an algorithm with incentives for information diffusion and show the approximate rate of social surplus that can be achieved. As a result, we show the incompatibility theorem of social surplus maximization and Nash stability with incentives for information diffusion, and furthermore, we show that the achievable approximation rate is 0.</p>

    DOI： 10.11517/pjsai.jsai2023.0_2f4gs503

    CiNii Research

  • Algorithms for coloring reconfiguration under recolorability digraphs Reviewed

    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 ）

    　More details

    Language：Others  

    Algorithms for coloring reconfiguration under recolorability digraphs

    DOI： 10.4230/LIPIcs.ISAAC.2022.4

    Scopus

    researchmap

  • Neighborhood Persistency of the Linear Optimization Relaxation of Integer Linear Optimization Reviewed

    312 - 323   2022.11

    　More details

    Language：Others  

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

  • Quantaloidal approach to constraint satisfaction Reviewed

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura

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

    　More details

    Language：Others  

    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

    　More details

    Language：Others  

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

  • An improved exact algorithm for multi-agent pathfinding problems

    SHIBATA Koshi, KIMURA Kei, TODO Taiki, YOKOO Makoto

    Proceedings of the Annual Conference of JSAI   JSAI2022 ( 0 )   1N1GS503 - 1N1GS503   2022

    　More details

    Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

    <p>The multi-agent pathfinding (MAPF) problem takes as input a set of agents with different starts and goals, and assigns a path that does not cause conflicts among the agents. There is a powerful exact algorithm called Meta-Agent Conflict Based Search (MA-CBS) for minimizing the sum of the costs for each agent to reach the goal, which is known to be NP-hard. The behavior of MA-CBS varies depending on a condition called the merge policy, but it is known that it requires a huge amount of execution time for some MAPF instances under the conventional static merge policy. In this paper, we propose a new merge policy that dynamically changes the properties of the algorithm, and show by computer experiments that the algorithm that implements the proposed merge policy runs efficiently on more various instances than the conventional one.</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

    　More details

  • Algorithms for coloring reconfiguration under recolorability digraphs Reviewed

    木村 慧

    Leibniz International Proceedings in Informatics   248   2022

    　More details

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

    Kei Kimura, Takuya Kamehashi

    Japan Journal of Industrial and Applied Mathematics   38 ( 3 )   823 - 858   2021.9

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.1007/s13160-021-00464-0

  • Quantaloidal approach to constraint satisfaction.

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura

    CoRR   abs/2107.01778   2021.7

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

  • Optimal Matroid Partitioning Problems Reviewed

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    Algorithmica   83 ( 6 )   1653 - 1676   2021.6

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.1007/s00453-021-00797-9

  • Trichotomy for the reconfiguration problem of integer linear systems. Reviewed

    Kei Kimura, Akira Suzuki

    Theor. Comput. Sci.   856   88 - 109   2021.2

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.tcs.2020.12.025

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

    Kei KIMURA

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

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.1587/transfun.2019eap1101

  • Trichotomy for the Reconfiguration Problem of Integer Linear Systems. Reviewed

    Kei Kimura, Akira Suzuki

    Proceedings of the 14th International Conference and Workshops on Algorithms and Computation, LNCS 12049   336 - 341   2020.3

    　More details

    Language：Others   Publishing type：Research paper (other academic)  

    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 Reviewed

    Higuchi Yuta, Kimura Kei

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

    　More details

    Language：Others  

    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

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

  • Approximating Partially Bounded Degree Deletion on Directed Graphs Reviewed

    Toshihiro Fujito, Kei Kimura, Yuki Mizuno

    Journal of Graph Algorithms and Applications   23 ( 5 )   759 - 780   2019.10

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.7155/jgaa.00511

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

    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

    　More details

    Language：Others  

    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

    　More details

    Language：Others   Publishing type：Research paper (other academic)  

    Linear Satisfiability Preserving Assignments (Extended Abstract).

    DOI： 10.24963/ijcai.2018/797

  • Maximum lifetime coverage problem with battery recovery effect Reviewed

    Norie Fu, Naonori Kakimura, Kei Kimura, Vorapong Suppakitpaisarn

    Sustainable Computing: Informatics and Systems   18   1 - 13   2018.6

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.suscom.2018.02.007

  • The Fewest Clues Problem of Picross 3D. Reviewed

    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

    　More details

    Language：Others  

    The Fewest Clues Problem of Picross 3D.

  • Approximating Partially Bounded Degree Deletion on Directed Graphs Reviewed

    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

    　More details

    Language：English   Publishing type：Research paper (other academic)  

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

  • Autark assignments of Horn CNFs Reviewed

    Kei Kimura, Kazuhisa Makino

    Japan Journal of Industrial and Applied Mathematics   35 ( 1 )   297 - 309   2018.3

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1007/s13160-017-0284-6

  • Linear Satisfiability Preserving Assignments Reviewed

    Kei Kimura, Kazuhisa Makino

    Journal of Artificial Intelligence Research   61   291 - 321   2018.2

    　More details

    Language：Others   Publishing type：Research paper (scientific journal)  

    DOI： 10.1613/jair.5658

    Repository Public URL： https://hdl.handle.net/2324/7172672

  • Optimal matroid partitioning problems Reviewed

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    Leibniz International Proceedings in Informatics, LIPIcs   92   51:1-51:13   2017.12

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.ISAAC.2017.51

  • Optimal Matroid Partitioning Problems Reviewed

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    CoRR   abs/1710.00950   2017.10

    　More details

    Language：Others  

    Optimal Matroid Partitioning Problems

  • Trichotomy for integer linear systems based on their sign patterns Reviewed

    Kei Kimura, Kazuhisa Makino

    DISCRETE APPLIED MATHEMATICS   200   67 - 78   2016.2

    　More details

    Language：English   Publishing type：Research paper (scientific journal)  

    DOI： 10.1016/j.dam.2015.07.004

  • Maximum Lifetime Coverage Problems with Battery Recovery Effects Reviewed

    Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, Naonori Kakimura

    2014 IEEE GLOBAL COMMUNICATIONS CONFERENCE (GLOBECOM 2014)   118 - 124   2014.12

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    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

    　More details

    Language：Others  

    Satisfiability Preserving Assignments and Their Local and Linear Forms

  • Trichotomy for Integer Linear Systems Based on Their Sign Patterns Reviewed

    Kei Kimura, Kazuhisa Makino

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

    　More details

    Language：English   Publishing type：Research paper (other academic)  

    DOI： 10.4230/LIPIcs.STACS.2012.613

▼display all

Presentations

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

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

    センシングフォ-ラム資料  2008.9 

    　More details

    Language：Japanese  

    Country：Japan  

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

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

    木村慧, 牧野和久

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

    　More details

    Language：Japanese  

    Country：Japan  

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

    木村 慧, 牧野 和久

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

    　More details

    Language：Japanese  

    Country：Japan  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    Trichotomy for Integer Linear Systems Based on Their Sign Patterns

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

    木村慧

    木村慧, 牧野和久, 電子情報通信学会, 岐阜大学  2013.3 

    　More details

    Language：Others  

    Country：Other  

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

    木村慧, 牧野和久

    電子情報通信学会大会講演論文集  2013.3 

    　More details

    Language：Japanese  

    Country：Japan  

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

    木村 慧, 牧野 和久

    電子情報通信学会総合大会講演論文集  2013.3 

    　More details

    Language：Japanese  

    Country：Japan  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    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 

    　More details

    Language：Others  

    Country：Other  

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

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

    木村慧

    木村慧, 牧野和久, 電子情報通信学会, 新潟大学  2014.3 

    　More details

    Language：Others  

    Country：Other  

  • A Complexity Index of Integer Linear Systems Based on Their Sign Patterns Invited International conference

    the 63th KPPY Combinatorics Workshop, Daegu, Korea  2014.3 

    　More details

    Language：English  

    Country：Other  

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

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

    木村慧, 牧野和久

    電子情報通信学会大会講演論文集(CD-ROM)  2014.3 

    　More details

    Language：Japanese  

    Country：Japan  

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

    木村慧, 牧野和久

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

    　More details

    Language：Japanese  

    Country：Japan  

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

    木村 慧, 牧野 和久

    電子情報通信学会総合大会講演論文集  2014.3 

    　More details

    Language：Japanese  

    Country：Japan  

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

    木村 慧, 牧野 和久

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

    　More details

    Language：Japanese  

    Country：Japan  

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    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 

    　More details

    Language：Others  

    Country：Other  

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

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

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

    木村慧

    電子情報通信学会大会講演論文集(CD-ROM)  2017.3 

    　More details

    Language：Japanese  

    Country：Japan  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    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 

    　More details

    Language：Others  

    Country：Other  

    Optimal Matroid Partitioning Problems

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

    樋口雄太

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

    　More details

    Language：Others  

    Country：Other  

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

    澁谷諒祐

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

    　More details

    Language：Others  

    Country：Other  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    Approximating Partially Bounded Degree Deletion on Directed Graphs

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

    樋口雄太, 木村慧

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

    　More details

    Language：Others  

    Country：Japan  

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

    澁谷諒祐, 木村慧

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

    　More details

    Language：Others  

    Country：Japan  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    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 

    　More details

    Language：Others  

    Country：Other  

    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 

    　More details

    Language：Others  

    Country：Other  

    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 

    　More details

    Language：Others  

    Country：Other  

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

  • Computational complexity of the reconfiguration problem of integer linear systems

    2020.2 

    　More details

    Language：Others  

    Country：Other  

    Computational complexity of the reconfiguration problem of integer linear systems

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    Trichotomy for the reconfiguration problem of integer linear systems

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    Quantaloidal approach to constraint satisfaction

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

    柴田航志

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

    　More details

    Language：Others  

    Country：Other  

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

    重信 賢直

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

    　More details

    Language：Others  

    Country：Other  

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

    澁谷諒祐

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

    　More details

    Language：Others  

    Country：Other  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    Neighborhood persistency of the linear optimization relaxation of integer linear optimization

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

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

    木村慧

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

    　More details

    Language：Others  

    Country：Other  

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

    吉田健人

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

    　More details

    Language：Others  

    Country：Other  

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

    横山健

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

    　More details

    Language：Others  

    Country：Other  

  • 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 

    　More details

    Language：Others  

    Country：Other  

    Algorithms for coloring reconfiguration under recolorability digraphs

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

    柴田 航志

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

    　More details

    Language：Others  

    Country：Other  

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

    米谷颯人

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

    　More details

    Language：Others  

    Country：Other  

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

    竹島遼太

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

    　More details

    Language：Others  

    Country：Other  

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

    若杉天真

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

    　More details

    Language：Others  

    Country：Other  

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

    横山 健

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

    　More details

    Language：Others  

    Country：Other  

  • 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 

    　More details

    Language：Others  

    Country：Other  

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

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

    赤星 雄太

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

    　More details

    Language：Others  

    Country：Other  

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

    吉田 健人

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

    　More details

    Language：Others  

    Country：Other  

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

    横山 健

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

    　More details

    Language：Others  

    Country：Other  

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

    木村慧

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

    　More details

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

    木村慧

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

    　More details

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

    横山 健

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    横山 健

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    横山健

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    重信 賢直

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

    　More details

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

    若杉天真

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    吉田健人

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    吉田 健人

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    柴田航志

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

    　More details

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

    柴田 航志

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    赤星 雄太

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    竹島遼太

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    澁谷諒祐

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

    　More details

  • 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 

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

  • Algorithms for coloring reconfiguration under recolorability digraphs

    Yuni Iwamasa

    2022.12 

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    Kei Kimura

    2023.12 

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

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

    米谷颯人

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

    　More details

    Presentation type：Oral presentation (general)  

    researchmap

▼display all

MISC

  • Optimal Matroid Partitioning Problems Reviewed

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    CoRR   2017.10

    　More details

    Language：Others  

    Optimal Matroid Partitioning Problems

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

    木村慧

    博士論文, 東京大学, 情報理工学系研究科   2015.3

    　More details

    Language：Others  

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

    木村慧

    修士論文, 東京大学, 情報理工学系研究科   2011.3

    　More details

    Language：Others  

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

    木村慧

    卒業論文, 東京大学, 工学部   2009.3

    　More details

    Language：Others  

Professional Memberships

  • THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS

    2014.1 - Present

    　 More details

  • THE OPERATIONS RESEARCH SOCIETY OF JAPAN

    2011.4 - Present

    　 More details

  • THE OPERATIONS RESEARCH SOCIETY OF JAPAN

  • THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS

Committee Memberships

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

    2024.4 - 2026.3   

    　 More details

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

    2021.6 - 2023.6   

    　 More details

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

    2019.7 - 2023.9   

    　 More details

    Committee type：Academic society

    researchmap

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

       

    　 More details

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

       

    　 More details

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

       

    　 More details

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

       

    　 More details

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

       

    　 More details

▼display all

Academic Activities

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

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

    　More details

Research Projects

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

    Grant number：21K17700  2021 - 2025

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

    木村 慧

    　 More details

    Grant type：Scientific research funding

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

    CiNii Research

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

    2020 - 2022

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

    　 More details

    Authorship：Principal investigator  Grant type：Contract research

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

    Grant number：19K22841  2019 - 2023

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

    牧野 和久, 木村 慧

    　 More details

    Authorship：Coinvestigator(s)  Grant type：Scientific research funding

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

    CiNii Research

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

    2019

    海外渡航旅費援助

    　 More details

    Authorship：Principal investigator  Grant type：Contract research

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

    2018

    研究者海外派遣助成

    　 More details

    Authorship：Principal investigator  Grant type：Contract research

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

    2018

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

    　 More details

    Authorship：Principal investigator  Grant type：On-campus funds, funds, etc.

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

    Grant number：15H06286  2015 - 2016

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

    　 More details

    Grant type：Scientific research funding

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

    2013 - 2014

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

    　 More details

    Grant type：Joint research

▼display all

Class subject

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

    2024.6 - 2024.8   Summer quarter

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

    2024.6 - 2024.8   Summer quarter

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

    2024.4 - 2025.3   Full year

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

    2024.4 - 2025.3   Full year

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

    2024.4 - 2025.3   Full year

  • 情報理工学読解

    2024.4 - 2024.9   First semester

  • 情報理工学論議Ⅰ

    2024.4 - 2024.9   First semester

  • 情報理工学論述Ⅰ

    2024.4 - 2024.9   First semester

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

    2024.4 - 2024.6   Spring quarter

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

    2024.4 - 2024.6   Spring quarter

  • (IUPE)Data Structure and Algorithms IB

    2023.12 - 2024.2   Winter quarter

  • Evidence-based Policy Making II

    2023.12 - 2024.2   Winter quarter

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

    2023.12 - 2024.2   Winter quarter

  • 情報理工学演示

    2023.10 - 2024.3   Second semester

  • 情報理工学論議Ⅱ

    2023.10 - 2024.3   Second semester

  • 情報理工学論述Ⅱ

    2023.10 - 2024.3   Second semester

  • (IUPE)Data Structure and Algorithms IA

    2023.10 - 2023.12   Fall quarter

  • Evidence-based Policy Making I

    2023.10 - 2023.12   Fall quarter

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

    2023.10 - 2023.12   Fall quarter

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

    2023.4 - 2024.3   Full year

  • 数学創発モデリング

    2023.4 - 2024.3   Full year

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

    2023.4 - 2024.3   Full year

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

    2023.4 - 2024.3   Full year

  • 情報理工学読解

    2023.4 - 2023.9   First semester

  • 情報理工学論議Ⅰ

    2023.4 - 2023.9   First semester

  • 情報理工学論述Ⅰ

    2023.4 - 2023.9   First semester

  • (IUPE)Data Structure and Algorithms IB

    2022.12 - 2023.2   Winter quarter

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

    2022.12 - 2023.2   Winter quarter

  • プログラミング技法

    2022.10 - 2023.3   Second semester

  • 情報理工学論議Ⅱ

    2022.10 - 2023.3   Second semester

  • 情報理工学論述Ⅱ

    2022.10 - 2023.3   Second semester

  • 情報理工学演示

    2022.10 - 2023.3   Second semester

  • プログラミング技法

    2022.10 - 2023.3   Second semester

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

    2022.10 - 2023.3   Second semester

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

    2022.10 - 2023.3   Second semester

  • (IUPE)Data Structure and Algorithms IA

    2022.10 - 2022.12   Fall quarter

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

    2022.10 - 2022.12   Fall quarter

  • 情報理工学講究

    2022.4 - 2023.3   Full year

  • 情報理工学演習

    2022.4 - 2023.3   Full year

  • 情報理工学研究Ⅰ

    2022.4 - 2023.3   Full year

  • 数学共創モデリング

    2022.4 - 2023.3   Full year

  • 数学共創概論I

    2022.4 - 2022.9   First semester

  • 情報理工学論議Ⅰ

    2022.4 - 2022.9   First semester

  • 情報理工学論述Ⅰ

    2022.4 - 2022.9   First semester

  • 情報理工学読解

    2022.4 - 2022.9   First semester

  • Data Structure and Algorithms IA,IB

    2022.4 - 2022.9   First semester

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

    2022.4 - 2022.9   First semester

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

    2021.10 - 2022.3   Second semester

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

    2021.10 - 2022.3   Second semester

  • 国際科学特論Ⅱ

    2021.10 - 2021.12   Fall quarter

▼display all

FD Participation

  • 2023.3   Role：Participation   Title：【シス情FD】独・蘭・台湾での産学連携を垣間見る-Industy 4.0・量子コンピューティング・先端半導体-

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2023.1   Role：Participation   Title：【シス情FD】若手教員による研究紹介⑦

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.10   Role：Participation   Title：【シス情FD】若手教員による研究紹介⑥

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.9   Role：Participation   Title：【シス情FD】研究機器の共用に向けて

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.7   Role：Participation   Title：【シス情FD】若手教員による研究紹介⑤

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.6   Role：Participation   Title：【シス情FD】電子ジャーナル等の今後について

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.5   Role：Participation   Title：【シス情FD】若手教員による研究紹介④「量子コンピュータ・システム・アーキテクチャの研究～道具になることを目指して～」

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.4   Role：Participation   Title：令和４年度 第１回全学ＦＤ（新任教員の研修）The 1st All-University FD (training for new faculty members) in FY2022

    Organizer：University-wide

  • 2022.4   Role：Participation   Title：【シス情FD】第4期中期目標・中期計画等について

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2022.3   Role：Participation   Title：全学FD:メンタルヘルス講演会

    Organizer：University-wide

  • 2022.1   Role：Participation   Title：【シス情FD】シス情関連の科学技術に対する国の政策動向（に関する私見）

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2021.12   Role：Participation   Title：【シス情FD】企業出身教員から見た大学

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2021.11   Role：Participation   Title：【シス情FD】若手教員による研究紹介　及び　研究費獲得のポイント等について③

    Organizer：[Undergraduate school/graduate school/graduate faculty]

  • 2021.10   Role：Participation   Title：【シス情FD】熊本高専と九大システム情報との交流・連携に向けて ー 3年半で感じた高専の実像 ー

    Organizer：[Undergraduate school/graduate school/graduate faculty]

▼display all

Other educational activity and Special note

  • 2023  Class Teacher 

  • 2022  Class Teacher 

Social Activities

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

    埼玉大学  2021.8

    　More details

    Audience： Infants,　Schoolchildren,　Junior students,　High school students

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

    2018

    　More details

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

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

    2017

    　More details

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

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

    2016

    　More details

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

Media Coverage

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

    FMラジオ広報「天伯之城 ギカダイ」  2018.2

    　More details

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

Activities contributing to policy formation, academic promotion, etc.

  • 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

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

    Program Commitee

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

    Program Commitee

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

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

▼display all