Researchers Information System

日本語に切り替えるswitch to english

Search for faculty members

Advanced SearchSearch by organization

Makino, Kazuhisa

Research Institute for Mathematical Sciences (RIMS) Professor

Makino, Kazuhisa
list
    Last Updated :2025/05/02

    Basic Information

    Affiliated programs (koza)

    • Graduate School of Science, 数学・数理解析専攻 解析数理講座, 教授

    Professional Memberships

    • 電気通信情報学会
    • 日本OR学会
    • 情報処理学会

    Academic Degree

    • 修士（工学）(京都大学)
    • 博士（工学）(京都大学)

    Research History

    • From 1997, To 2000
      大阪大学大学院
    • From 1997, To 2000
      Osaka University, Research Associate
    • 旧所属 大阪大学 大学院基礎工学研究科 システム創成専攻 社会システム数理領域, 講師

    ID,URL

    researchmap URL

    list
      Last Updated :2025/05/02

      Research

      Research Interests

      • Game Theory
      • Algorithm Theory
      • Optimization
      • Discrete Mathematics

      Research Areas

      • Natural sciences, Applied mathematics and statistics
      • Informatics, Computational science

      Papers

      • Minimizing submodular functions on diamonds via generalized fractional matroid matchings
        Satoru Fujishige; Tamás Király; Kazuhisa Makino; Kenjiro Takazawa; Shin ichi Tanigawa
        Journal of Combinatorial Theory. Series B, Nov. 2022
      • O(n log2 n) an algorithm for a sink location problem in dynamic tree networks
        Satoko Mamada; Takeaki Uno; Kazuhisa Makino; Satoru Fujishige
        IFIP Advances in Information and Communication Technology, 2004
      • The maximum latency and identification of positive boolean functions
        Kazuhisa Makino; Toshihide Ibaraki
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1994
      • Fully consistent extensions of partially defined boolean functions with missing bits
        Endre Boros; Toshihide Ibaraki; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2000
      • Boolean analysis of incomplete examples
        Endre Boros; Toshihide Ibaraki; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1996
      • On the Sprague–Grundy function of extensions of proper Nim
        Endre Boros; Vladimir Gurvich; Nhan Bao Ho; Kazuhisa Makino
        International Journal of Game Theory, 01 Sep. 2021
      • Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
        Khaled Elbassioni; Kazuhisa Makino
        SIAM Journal on Discrete Mathematics, 2020
      • Sprague-Grundy function of matroids and related hypergraphs
        Endre Boros; Vladimir Gurvich; Nhan Bao Ho; Kazuhisa Makino; Peter Mursic
        Theoretical Computer Science, 24 Dec. 2019
      • Oracle-based primal-dual algorithms for packing and covering semidefinite programs
        Khaled Elbassioni; Kazuhisa Makino
        Leibniz International Proceedings in Informatics, LIPIcs, 01 Sep. 2019
      • A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        Information and Computation, 01 Aug. 2019
      • Sprague–Grundy function of symmetric hypergraphs
        Endre Boros; Vladimir Gurvich; Nhan Bao Ho; Kazuhisa Makino; Peter Mursic
        Journal of Combinatorial Theory. Series A, 01 Jul. 2019
      • A Multiplicative Weight Updates Algorithm for Packing and Covering Semi-infinite Linear Programs
        Khaled Elbassioni; Kazuhisa Makino; Waleed Najy
        Algorithmica, 01 Jun. 2019
      • A combinatorial min-max theorem and minimization of pure-horn functions
        Endre Boros; Ondřej Čepek; Kazuhisa Makino
        International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016, 2016
      • Envy-free relaxations for goods, chores, and mixed items
        Kristóf Bérczi; Erika R. Bérczi-Kovács; Endre Boros; Fekadu Tolessa Gedefa; Naoyuki Kamiyama; Telikepalli Kavitha; Yusuke Kobayashi; Kazuhisa Makino
        Theoretical Computer Science, Jun. 2024
      • Characterizing the integer points in 2-decomposable polyhedra by closedness under operations.
        Kei Kimura; Kazuhisa Makino; Shota Yamada; Ryo Yoshizumi
        CoRR, 2024
      • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems.
        Kei Kimura; Kazuhisa Makino
        CoRR, 2023
      • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems.
        Kei Kimura; Kazuhisa Makino
        ISAAC, 2023
      • Towards Optimal Subsidy Bounds for Envy-Freeable Allocations.
        Yasushi Kawase; Kazuhisa Makino; Hanna Sumita; Akihisa Tamura; Makoto Yokoo
        AAAI, 2024
      • A fair and truthful mechanism with limited subsidy
        Hiromichi Goko; Ayumi Igarashi; Yasushi Kawase; Kazuhisa Makino; Hanna Sumita; Akihisa Tamura; Yu Yokoi; Makoto Yokoo
        Games and Economic Behavior, Mar. 2024
      • A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem.
        Yuki Amano; Kazuhisa Makino
        Theory and Applications of Models of Computation - 17th Annual Conference(TAMC), 2022
      • A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem.
        Yuki Amano; Kazuhisa Makino
        CoRR, 2020
      • Towards Optimal Subsidy Bounds for Envy-freeable Allocations.
        Yasushi Kawase; Kazuhisa Makino; Hanna Sumita; Akihisa Tamura; Makoto Yokoo
        CoRR, 2023
      • Trade-offs among degree, diameter, and number of paths.
        Toshimasa Ishii; Akitoshi Kawamura; Yusuke Kobayashi 0001; Kazuhisa Makino
        Discret. Appl. Math., 2023
      • Online Scheduling on Identical Machines with a Metric State Space.
        Hiromichi Goko; Akitoshi Kawamura; Yasushi Kawase; Kazuhisa Makino; Hanna Sumita
        39th International Symposium on Theoretical Aspects of Computer Science(STACS), 2022
      • Fair and Truthful Mechanism with Limited Subsidy.
        Hiromichi Goko; Ayumi Igarashi 0001; Yasushi Kawase; Kazuhisa Makino; Hanna Sumita; Akihisa Tamura; Yu Yokoi; Makoto Yokoo
        21st International Conference on Autonomous Agents and Multiagent Systems(AAMAS), 2022
      • Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas.
        Kazuhisa Makino; Shuichi Miyazaki; Yu Yokoi
        SAGT, 2022
      • Reallocation Problems with Minimum Completion Time.
        Toshimasa Ishii; Jun Kawahara; Kazuhisa Makino; Hirotaka Ono
        COCOON, 2022
      • Fair Ride Allocation on a Line.
        Yuki Amano; Ayumi Igarashi; Yasushi Kawase; Kazuhisa Makino; Hirotaka Ono
        SAGT, 2022
      • Posimodular Function Optimization.
        Magnús M. Halldórsson; Toshimasa Ishii; Kazuhisa Makino; Kenjiro Takazawa
        Algorithmica, 2022
      • Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties.
        Hiromichi Goko; Kazuhisa Makino; Shuichi Miyazaki; Yu Yokoi
        STACS, 2022
      • Optimal Matroid Partitioning Problems
        Yasushi Kawase; Kei Kimura; Kazuhisa Makino; Hanna Sumita
        Algorithmica, Jun. 2021
      • Reallocation Problems with Minimum Completion Time.
        Toshimasa Ishii; Jun Kawahara; Kazuhisa Makino; Hirotaka Ono
        CoRR, 2021
      • Fair and Truthful Mechanism with Limited Subsidy.
        Hiromichi Goko; Ayumi Igarashi; Yasushi Kawase; Kazuhisa Makino; Hanna Sumita; Akihisa Tamura; Yu Yokoi; Makoto Yokoo
        CoRR, 2021
      • Fair Ride Allocation on a Line.
        Yuki Amano; Ayumi Igarashi; Yasushi Kawase; Kazuhisa Makino; Hirotaka Ono
        CoRR, 2020
      • The Steiner Problem for Count Matroids.
        Tibor Jordán; Yusuke Kobayashi; Ryoga Mahara; Kazuhisa Makino
        Combinatorial Algorithms - 31st International Workshop(IWOCA), 2020, Peer-reviewed
      • Ranking top-k trees in tree-based phylogenetic networks
        Momoko Hayamizu; Kazuhisa Makino
        arXiv:1904.12432 [math.CO], Apr. 2019
      • Total dual integrality of the linear complementarity problem.
        Hanna Sumita; Naonori Kakimura; Kazuhisa Makino
        Annals OR, 2019, Peer-reviewed
      • Online Knapsack Problems with a Resource Buffer.
        Xin Han; Yasushi Kawase; Kazuhisa Makino; Haruki Yokomaku
        CoRR, 2019, Peer-reviewed
      • Online Knapsack Problems with a Resource Buffer.
        Xin Han; Yasushi Kawase; Kazuhisa Makino; Haruki Yokomaku
        30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics(ISAAC), 2019, Peer-reviewed
      • Unit Cost Buyback Problem.
        Yasushi Kawase; Xin Han; Kazuhisa Makino
        Theory Comput. Syst., 2019, Peer-reviewed
      • Surrogate optimization for p-norms.
        Yasushi Kawase; Kazuhisa Makino
        Discrete Optimization, 2019, Peer-reviewed
      • Proportional cost buyback problem with weight bounds.
        Yasushi Kawase; Xin Han; Kazuhisa Makino
        Theor. Comput. Sci., 2019, Peer-reviewed
      • Parameterized Edge Hamiltonicity
        Michael Lampis; Kazuhisa Makino; Valia Mitsou; Yushi Uno
        Discrete Applied Mathematics, Oct. 2018
      • Enumerating vertices of 0/1-Polyhedra associated with 0/1-totally unimodular matrices
        Khaled Elbassioni; Kazuhisa Makino
        Leibniz International Proceedings in Informatics, LIPIcs, 01 Jun. 2018, Peer-reviewed
      • Markov decision processes and stochastic games with total effective payoff
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        Annals of Operations Research, 28 May 2018, Peer-reviewed
      • On the Sprague–Grundyfunction of EXACTk-NIM
        Endre Boros; Vladimir Gurvich; Nhan Bao Ho; Kazuhisa Makino; Peter Mursic
        Discrete Applied Mathematics, 20 Apr. 2018, Peer-reviewed
      • A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        Dynamic Games and Applications, 01 Mar. 2018, Peer-reviewed
      • Autark assignments of Horn CNFs
        Kei Kimura; Kazuhisa Makino
        Japan Journal of Industrial and Applied Mathematics, 01 Mar. 2018, Peer-reviewed
      • Online knapsack problem under concave functions
        Xin Han; Qinyang Chen; Kazuhisa Makino
        Theoretical Computer Science, 2018, Peer-reviewed
      • Linear Satisfiability Preserving Assignments (Extended Abstract).
        Kei Kimura; Kazuhisa Makino
        Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden., 2018, Peer-reviewed
      • Linear Satisfiability Preserving Assignments.
        Kei Kimura; Kazuhisa Makino
        J. Artif. Intell. Res., 2018, Peer-reviewed
      • Optimal Composition Ordering Problems for Piecewise Linear Functions.
        Yasushi Kawase; Kazuhisa Makino; Kento Seimi
        Algorithmica, 2018, Peer-reviewed
      • A convex programming-based algorithm for mean payoff stochastic games with perfect information
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        OPTIMIZATION LETTERS, Dec. 2017, Peer-reviewed
      • Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions
        Endre Boros; Khaled Elbassioni; Mahmoud Fouz; Vladimir Gurvich; Kazuhisa Makino; Bodo Manthey
        Algorithmica, 19 Sep. 2017, Peer-reviewed
      • Parameterized Complexity of Sparse Linear Complementarity Problems
        Hanna Sumita; Naonori Kakimura; Kazuhisa Makino
        ALGORITHMICA, Sep. 2017, Peer-reviewed
      • A representation of antimatroids by Horn rules and its application to educational systems
        Hiyori Yoshikawa; Hiroshi Hirai; Kazuhisa Makino
        Journal of Mathematical Psychology, 01 Apr. 2017, Peer-reviewed
      • A nested family of -total effective rewards for positional games
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        INTERNATIONAL JOURNAL OF GAME THEORY, Mar. 2017, Peer-reviewed
      • Strong duality in horn minimization
        Endre Boros; Ondřej Čepek; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2017, Peer-reviewed
      • Posimodular function optimization
        Magnús M. Halldórsson; Toshimasa Ishii; Kazuhisa Makino; Kenjiro Takazawa
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2017, Peer-reviewed
      • Online knapsack problem under concave functions
        Xin Han; Ning Ma; Kazuhisa Makino; He Chen
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2017, Peer-reviewed
      • A multiplicative weights update algorithm for packing and covering semi-infinite linear programs
        Khaled Elbassioni; Kazuhisa Makino; Waleed Najy
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2017, Peer-reviewed
      • Optimal Matroid Partitioning Problems.
        Yasushi Kawase; Kei Kimura; Kazuhisa Makino; Hanna Sumita
        28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, 2017, Peer-reviewed
      • Optimal composition ordering problems for piecewise linear functions
        Yasushi Kawase; Kazuhisa Makino; Kento Seimi
        Leibniz International Proceedings in Informatics, LIPIcs, 01 Dec. 2016, Peer-reviewed
      • Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden subgames
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino; Vladimir Oudalov
        INTERNATIONAL JOURNAL OF GAME THEORY, Nov. 2016, Peer-reviewed
      • Online minimization knapsack problem
        Xin Han; Kazuhisa Makino
        THEORETICAL COMPUTER SCIENCE, Jan. 2016, Peer-reviewed
      • Trichotomy for integer linear systems based on their sign patterns.
        Kei Kimura; Kazuhisa Makino
        Discrete Applied Mathematics, 2016, Peer-reviewed
      • Surrogate Optimization for p-Norms.
        Yasushi Kawase; Kazuhisa Makino
        27th International Symposium on Algorithms and Computation, ISAAC 2016, December 12-14, 2016, Sydney, Australia, 2016, Peer-reviewed
      • On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets
        Khaled Elbassioni; Kazuhisa Makino; Kurt Mehlhorn; Fahimeh Ramezani
        ALGORITHMICA, Oct. 2015, Peer-reviewed
      • Deterministic random walks on finite graphs
        Shuji Kijima; Kentaro Koga; Kazuhisa Makino
        RANDOM STRUCTURES & ALGORITHMS, Jul. 2015, Peer-reviewed
      • Algorithms and Computation: 26th International Symposium, ISAAC 2015 Nagoya, Japan, December 9-11, 2015 Proceedings
        Khaled Elbassioni; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2015, Peer-reviewed
      • Parameterized Algorithms for Parity Games
        Jakub Gajarsky; Michael Lampis; Kazuhisa Makino; Valia Mitsou; Sebastian Ordyniak
        MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT II, 2015, Peer-reviewed
      • Parameterized Complexity of Sparse Linear Complementarity Problems.
        Hanna Sumita; Naonori Kakimura; Kazuhisa Makino
        10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, 2015, Peer-reviewed
      • The Linear Complementarity Problems with a Few Variables per Constraint.
        Hanna Sumita; Naonori Kakimura; Kazuhisa Makino
        Math. Oper. Res., 2015, Peer-reviewed
      • Proportional Cost Buyback Problem with Weight Bounds.
        Yasushi Kawase; Xin Han; Kazuhisa Makino
        Combinatorial Optimization and Applications - 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings, 2015, Peer-reviewed
      • Parameterized Edge Hamiltonicity
        Michael Lampis; Kazuhisa Makino; Valia Mitsou; Yushi Uno
        GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2014, Peer-reviewed
      • Deterministic Random Walks on Finite Graphs.
        Shuji Kijima; Kentaro Koga; Kazuhisa Makino
        Proceedings of the 9th Meeting on Analytic Algorithmics and Combinatorics(ANALCO), 2012
      • Posi-Modular Systems with Modulotone Requirements under Permutation Constraints.
        Toshimasa Ishii; Kazuhisa Makino
        Discrete Math., Alg. and Appl., 2010, Peer-reviewed
      • Generating Vertices of Polyhedra and Related Problems of Monotone Generation
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        POLYHEDRAL COMPUTATION, 2009, Peer-reviewed
      • New Results for Horn Cores and Envelopes of Horn Disjunctions
        Thomas Eiter; Kazuhisa Makino
        ECAI 2008, PROCEEDINGS, 2008, Peer-reviewed
      • On the Boolean Connectivity Problem for Horn Relations (extended abstract)
        Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto
        Proceedings of the 10th International Conference on Theory and Applications of Satisfiability Testing (SAT), May 2007, Peer-reviewed
      • A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem.
        Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto 0001
        Electron. Colloquium Comput. Complex., 2007
      • Generating minimal spanning k-vertex connected subgraphs
        Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino; Gabor Rudolf
        COMPUTING AND COMBINATORICS, PROCEEDINGS, 2007, Peer-reviewed
      • On the fractional chromatic number of monotone self-dual Boolean functions
        Daya Ram Gaur; Kazuhisa Makino
        FRONTIERS IN ALGORITHMICS, PROCEEDINGS, 2007, Peer-reviewed
      • Enumerating spanning and connected subsets in graphs and matroids
        L. Khachiyan; E. Boros; K. Borys; K. Elbassioni; V. Gurvich; K. Makino
        ALGORITHMS - ESA 2006, PROCEEDINGS, 2006, Peer-reviewed
      • Minimum transversals in posi-modular systems
        Mariko Sakashita; Kazuhisa Makino; Hiroshi Nagamochi; Satoru Fujishige
        ALGORITHMS - ESA 2006, PROCEEDINGS, 2006, Peer-reviewed
      • A polynomial time algorithm for evacuation problem in tree dynamic networks with multiple exits
        Mamnada S; Uno T; Makino K; Fujishige S
        Proceedings of the SICE Annual Conference, 2005, Peer-reviewed
      • New Algorithms for Enumerating All Maximal Cliques
        Kazuhisa Makino; Takeaki Uno
        Lecture Notes in Computer Science (SWAT2004), Jul. 2004, Peer-reviewed
      • Generating paths and cuts in multi-pole (Di)graphs
        E Boros; K Elbassioni; Gurvich, V; L Khachiyan; K Makino
        MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS, 2004, Peer-reviewed
      • An O(nlog^2n) Algorithm for the Optimal Sink Location Problem on Dynamic Tree Networks
        間々田 聡子; 宇野 毅明; 牧野 和久; 藤重 悟
        第93回情報処理学会アルゴリズム研究会, Jan. 2004
      • The evacuation problem, dynamic network flows, and algorithms
        S Mamada; K Makino; T Takabatake; S Fujishige
        SICE 2003 ANNUAL CONFERENCE, VOLS 1-3, 2003, Peer-reviewed
      • An intersection inequality for discrete distributions and related generation problems
        E Boros; K Elbassioni; Gurvich, V; L Khachiyan; K Makino
        AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2003, Peer-reviewed
      • Generating all abductive explanations for queries on propositional horn theories
        T Eiter; K Makino
        COMPUTER SCIENCE LOGIC, PROCEEDINGS, 2003, Peer-reviewed
      • Abduction and the dualization problem
        T Eiter; K Makino
        DISCOVERY SCIENCE, PROCEEDINGS, 2003, Peer-reviewed
      • The evacuation problem and related topics
        S Fujishige; K Makino; T Takabatake; S Mamada
        SICE 2002: PROCEEDINGS OF THE 41ST SICE ANNUAL CONFERENCE, VOLS 1-5, 2002, Peer-reviewed
      • On generating all minimal integer solutions for a monotone system of linear inequalities
        E Boros; K Elbassioni; Gurvich, V; L Khachiyan; K Makino
        AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING, 2001, Peer-reviewed
      • Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
        B Rutcor; Gurvich, V; L Khachiyan; K Makino
        SIAM JOURNAL ON COMPUTING, Apr. 2000, Peer-reviewed
      • Finding Essential Attributes in Binary Data.
        Endre Boros; Takashi Horiyama; Toshihide Ibaraki; Kazuhisa Makino; Mutsunori Yagiura
        Intelligent Data Engineering and Automated Learning - IDEAL 2000, Data Mining, Financial Engineering, and Intelligent Agents(IDEAL), 2000
      • Logical analysis of data with decomposable structures
        H Ono; K Makino; T Ibaraki
        COMPUTING AND COMBINATORICS, PROCEEDINGS, 2000, Peer-reviewed
      • Generating partial and multiple transversals of a hypergraph
        E Boros; Gurvich, V; L Khachiyan; K Makino
        AUTOMATA LANGUAGES AND PROGRAMMING, 2000, Peer-reviewed
      • Max- and min-neighborhood monopolies
        K Makino; M Yamashita; T Kameda
        ALGORITHM THEORY - SWAT 2000, 2000, Peer-reviewed
      • Locating sources to meet flow demands in undirected networks
        K Arata; S Iwata; K Makino; S Fujishige
        ALGORITHM THEORY - SWAT 2000, 2000, Peer-reviewed
      • Inner-core and outer-core functions of partially defined Boolean functions
        K Makino; T Ibaraki
        DISCRETE APPLIED MATHEMATICS, Oct. 1999, Peer-reviewed
      • Computing intersections of Horn theories for reasoning with models
        T Eiter; T Ibaraki; K Makino
        ARTIFICIAL INTELLIGENCE, May 1999, Peer-reviewed
      • On Minimum Edge Ranking Spanning Trees
        Kazuhisa Makino; Yushi Uno; Toshihide Ibaraki
        Lecture Notes in Computer Science, 1999
      • A linear time algorithm for recognizing regular boolean functions
        Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1999, Peer-reviewed
      • Data analysis by positive decision trees
        K Makino; T Suda; H Ono; T Ibaraki
        IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, Jan. 1999, Peer-reviewed
      • On the difference of horn theories (Extended abstract)
        T Eiter; T Ibaraki; K Makino
        STACS'99 - 16TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, 1999, Peer-reviewed
      • Convexity of Elementary Flow Games.
        永持仁; 牧野和久; ZENG D‐Z; 村田真紀; 茨木俊秀
        電子情報通信学会論文誌 D-1, Jun. 1998, Peer-reviewed
      • Error-free and best-fit extensions of partially defined Boolean functions
        E Bores; T Ibaraki; K Makino
        INFORMATION AND COMPUTATION, Feb. 1998, Peer-reviewed
      • Disjunctions of horn theories and their cores
        T Eiter; T Ibaraki; K Makino
        ALGORITHMS AND COMPUTATIONS, 1998, Peer-reviewed
      • Two-face Horn extensions
        T Eiter; T Ibaraki; K Makino
        ALGORITHMS AND COMPUTATION, PROCEEDINGS, 1997, Peer-reviewed
      • Monotone extensions of Boolean data sets
        E Boros; T Ibaraki; K Makino
        ALGORITHMIC LEARNING THEORY, 1997, Peer-reviewed
      • Markov decision processes and stochastic games with total effective payoff
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        Leibniz International Proceedings in Informatics, LIPIcs, 01 Feb. 2015, Peer-reviewed
      • Randomized algorithms for online knapsack problems
        Xin Han; Yasushi Kawase; Kazuhisa Makino
        THEORETICAL COMPUTER SCIENCE, Jan. 2015, Peer-reviewed
      • Online removable knapsack problem under convex function
        Xin Han; Yasushi Kawase; Kazuhisa Makino; He Guo
        THEORETICAL COMPUTER SCIENCE, Jun. 2014, Peer-reviewed
      • Augmenting Edge-Connectivity between Vertex Subsets
        Toshimasa Ishii; Kazuhisa Makino
        ALGORITHMICA, May 2014, Peer-reviewed
      • A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014), 2014, Peer-reviewed
      • Derandomizing the HSSW Algorithm for 3-SAT
        Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto
        ALGORITHMICA, Oct. 2013, Peer-reviewed
      • On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makin
        OPERATIONS RESEARCH LETTERS, Jul. 2013, Peer-reviewed
      • On Canonical Forms for Zero-Sum Stochastic Mean Payoff Games
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        DYNAMIC GAMES AND APPLICATIONS, Jun. 2013, Peer-reviewed
      • Nash equilibria with minimum potential in undirected broadcast games
        Yasushi Kawase; Kazuhisa Makino
        THEORETICAL COMPUTER SCIENCE, Apr. 2013, Peer-reviewed
      • Unit Cost Buyback Problem
        Yasushi Kawase; Xin Han; Kazuhisa Makino
        ALGORITHMS AND COMPUTATION, 2013, Peer-reviewed
      • ROBUST MATCHINGS AND MATROID INTERSECTIONS
        Ryo Fujita; Yusuke Kobayashi; Kazuhisa Makino
        SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, Peer-reviewed
      • ROBUST INDEPENDENCE SYSTEMS
        Naonori Kakimura; Kazuhisa Makino
        SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, Peer-reviewed
      • On randomized fictitious play for approximating saddle points over convex sets
        Khaled Elbassioni; Kazuhisa Makino; Kurt Mehlhorn; Fahimeh Ramezani
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, Peer-reviewed
      • Randomized algorithms for removable online knapsack problems
        Xin Han; Yasushi Kawase; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, Peer-reviewed
      • Sparse linear complementarity problems
        Hanna Sumita; Naonori Kakimura; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, Peer-reviewed
      • Online Unweighted Knapsack Problem with Removal Cost
        Xin Han; Yasushi Kawase; Kazuhisa Makino
        ALGORITHMICA, Sep. 2014, Peer-reviewed
      • A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and a few random positions
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, Peer-reviewed
      • Deductive Inference for the Interiors and Exteriors of Horn Theories
        Kazuhisa Makino; Hirotaka Ono
        ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, Aug. 2012, Peer-reviewed
      • On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like n-person games
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        DISCRETE MATHEMATICS, Feb. 2012, Peer-reviewed
      • Trichotomy for integer linear systems based on their sign patterns
        Kei Kimura; Kazuhisa Makino
        Leibniz International Proceedings in Informatics, LIPIcs, 2012, Peer-reviewed
      • Computing knapsack solutions with cardinality robustness
        Naonori Kakimura; Kazuhisa Makino; Kento Seimi
        JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS, 2012, Peer-reviewed
      • Online knapsack problem with removal cost
        Xin Han; Yasushi Kawase; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, Peer-reviewed
      • Nash equilibria with minimum potential in undirected broadcast games
        Yasushi Kawase; Kazuhisa Makino
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, Peer-reviewed
      • FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS
        Khaled Elbassioni; Amr Elmasry; Kazuhisa Makino
        INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, Oct. 2011, Peer-reviewed
      • On the readability of monotone Boolean formulae
        Khaled Elbassioni; Kazuhisa Makino; Imran Rauf
        JOURNAL OF COMBINATORIAL OPTIMIZATION, Oct. 2011, Peer-reviewed
      • Nash-solvable two-person symmetric cycle game forms
        Endre Boros; Vladimir Gurvich; Kazuhisa Makino; Wei Shao
        DISCRETE APPLIED MATHEMATICS, Sep. 2011, Peer-reviewed
      • An exact algorithm for the Boolean connectivity problem for k-CNF
        Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto
        THEORETICAL COMPUTER SCIENCE, Aug. 2011, Peer-reviewed
        Access this paper :
      • Logical analysis of data: classification with justification
        Endre Boros; Yves Crama; Peter L. Hammer; Toshihide Ibaraki; Alexander Kogan; Kazuhisa Makino
        ANNALS OF OPERATIONS RESEARCH, Aug. 2011, Peer-reviewed
      • Computing Knapsack Solutions with Cardinality Robustness
        Naonori Kakimura; Kazuhisa Makino; Kento Seimi
        ALGORITHMS AND COMPUTATION, 2011, Peer-reviewed
      • Derandomizing HSSW Algorithm for 3-SAT.
        Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto 0001
        Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, Peer-reviewed
      • Robust Independence Systems
        Naonori Kakimura; Kazuhisa Makino
        Automata, Languages and Programming, ICALP, Pt I, 2011, Peer-reviewed
      • Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
        Endre Boros; Khaled Elbassioni; Mahmoud Fouz; Vladimir Gurvich; Kazuhisa Makino; Bodo Manthey
        Automata, Languages and Programming, ICALP, Pt I, 2011, Peer-reviewed
      • Caching Is Hard-Even in the Fault Model
        Marek Chrobak; Gerhard J. Woeginger; Kazuhisa Makino; Haifeng Xu
        ALGORITHMICA, Aug. 2012, Peer-reviewed
      • On the Boolean connectivity problem for Horn relations
        Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto
        DISCRETE APPLIED MATHEMATICS, Nov. 2010, Peer-reviewed
      • Online removable knapsack with limited cuts
        Xin Han; Kazuhisa Makino
        THEORETICAL COMPUTER SCIENCE, Oct. 2010, Peer-reviewed
      • Acyclic, or totally tight, two-person game forms: Characterization and main properties
        Endre Boros; Vladimir Gurvich; Kazuhisa Makino; David Papp
        DISCRETE MATHEMATICS, Apr. 2010, Peer-reviewed
      • On effectivity functions of game forms
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        GAMES AND ECONOMIC BEHAVIOR, Mar. 2010, Peer-reviewed
      • Robust Matchings and Matroid Intersections
        Ryo Fujita; Yusuke Kobayashi; Kazuhisa Makino
        ALGORITHMS-ESA 2010, PT II, 2010, Peer-reviewed
      • Caching Is Hard - Even in the Fault Model
        Marek Chrobak; Gerhard J. Woeginger; Kazuhisa Makino; Haifeng Xu
        ALGORITHMS-ESA 2010, 2010, Peer-reviewed
      • LEFT-TO-RIGHT MULTIPLICATION FOR MONOTONE BOOLEAN DUALIZATION
        Endre Boros; Khaled Elbassioni; Kazuhisa Makino
        SIAM JOURNAL ON COMPUTING, 2010, Peer-reviewed
      • An Exact Algorithm for the Boolean Connectivity Problem for k-CNF
        Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto
        THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2010, PROCEEDINGS, 2010, Peer-reviewed
      • A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 2010, Peer-reviewed
      • Minimal and locally minimal games and game forms
        Endre Boros; Vladimir Gurvich; Kazuhisa Makino
        DISCRETE MATHEMATICS, Jul. 2009, Peer-reviewed
      • On the fractional chromatic number of monotone self-dual Boolean functions
        Daya Ram Gaur; Kazuhisa Makino
        DISCRETE MATHEMATICS, Mar. 2009, Peer-reviewed
      • Online Minimization Knapsack Problem
        Xin Han; Kazuhisa Makino
        APPROXIMATION AND ONLINE ALGORITHMS, 2010, Peer-reviewed
      • On the Readability of Monotone Boolean Formulae
        Khaled Elbassioni; Kazuhisa Makino; Imran Rauf
        COMPUTING AND COMBINATORICS, PROCEEDINGS, 2009, Peer-reviewed
      • Online Knapsack Problems with Limited Cuts
        Xin Han; Kazuhisa Makino
        ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, Peer-reviewed
      • Posi-modular Systems with Modulotone Requirements under Permutation Constraints
        Toshimasa Ishii; Kazuhisa Makino
        ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, Peer-reviewed
      • MINIMUM TRANSVERSALS IN POSIMODULAR SYSTEMS
        Mariko Sakashita; Kazuhisa Makino; Hiroshi Nagamochi; Satoru Fujishige
        SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, Peer-reviewed
      • A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
        Endre Boros; Kazuhisa Makino
        AUTOMATA, LANGUAGES AND PROGRAMMING, PT I, 2009, Peer-reviewed
      • Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
        Khaled Elbassioni; Kazuhisa Makino; Imran Rauf
        ALGORITHMS - ESA 2009, PROCEEDINGS, 2009, Peer-reviewed
      • Generating cut conjunctions in graphs and related problems
        Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        ALGORITHMICA, Jul. 2008, Peer-reviewed
      • Minimizing a monotone concave function with laminar covering constraints
        Mariko Sakashita; Kazuhisa Makino; Satoru Fujishige
        DISCRETE APPLIED MATHEMATICS, Jun. 2008, Peer-reviewed
      • Computational aspects of monotone dualization: A brief survey
        Thomas Eiter; Kazuhisa Makino; Georg Gottlob
        DISCRETE APPLIED MATHEMATICS, Jun. 2008, Peer-reviewed
      • Minimum cost source location problems with flow requirements
        Mariko Sakashita; Kazuhisa Makino; Satoru Fujishige
        ALGORITHMICA, Apr. 2008, Peer-reviewed
      • Deductive Inference for the Interiors and Exteriors of Horn Theories
        Kazuhisa Makino; Hirotaka Ono
        ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2008, Peer-reviewed
      • On Berge multiplication for monotone Boolean dualization
        Endre Boros; Khaled Elbassioni; Kazuhisa Makino
        AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, PROCEEDINGS, 2008, Peer-reviewed
      • A complete characterization of Nash-solvability of bimatrix games in terms of the exclusion of certain 2 x 2 subgames
        Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino; Vladimir Oudalov
        COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2008, Peer-reviewed
      • Enumerating spanning and connected subsets in graphs and matroids
        Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, Dec. 2007, Peer-reviewed
      • Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
        Leonid Khachiyan; Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        THEORETICAL COMPUTER SCIENCE, Jun. 2007, Peer-reviewed
      • A special issue on the 50th anniversary of the Operations Research Society of Japan - Introduction
        Naoki Katoh; Hiroshi Yabe; Shoji Kasahara; Kazuhisa Makino; Tomomi Matsui; Hiroshi Morita; Masakazu Muramatsu; Atsuo Suzuki
        JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, Dec. 2007, Peer-reviewed
      • On computing all abductive explanations from a propositional horn theory
        Thomas Eiter; Kazuhisa Making
        JOURNAL OF THE ACM, 2007, Peer-reviewed
      • Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
        Leonid Khachiyan; Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino
        DISCRETE APPLIED MATHEMATICS, Jan. 2007, Peer-reviewed
      • An O(n log(2) n) algorithm for the optimal sink location problem in dynamic tree networks
        Satoko Mamada; Takeaki Uno; Kazuhisa Makino; Satoru Fujishige
        DISCRETE APPLIED MATHEMATICS, Nov. 2006, Peer-reviewed
      • How to collect balls moving in the Euclidean plane
        Yuichi Asahiro; Takashi Horiyama; Kazuhisa Makino; Hirotaka Ono; Toshinori Sakuma; Masafumi Yamashita
        DISCRETE APPLIED MATHEMATICS, Nov. 2006, Peer-reviewed
      • Minimum edge ranking spanning trees of split graphs
        Kazuhisa Makino; Yushi Uno; Toshihide Ibaraki
        DISCRETE APPLIED MATHEMATICS, Nov. 2006, Peer-reviewed
      • Minimum cost source location problems with flow requirements
        M Sakashita; K Makino; S Fujishige
        LATIN 2006: THEORETICAL INFORMATICS, 2006, Peer-reviewed
      • On the complexity of some enumeration problems for matroids
        L Khachiyan; E Boros; K Elbassioni; Gurvich, V; K Makino
        SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, Peer-reviewed
      • A tree partitioning problem arising from an evacuation problem in tree dynamic networks
        S Mamada; T Uno; K Makino; S Fujishige
        JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, Sep. 2005, Peer-reviewed
      • Special section on discrete mathematics and its applications
        K Makino
        IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, May 2005, Peer-reviewed
      • Preface
        T. Arai; S. Yamamoto; K. Makino
        Systems and Human Science - For Safety, Security and Dependability, 2005, Peer-reviewed
      • An evacuation problem in tree dynamic networks with multiple exits
        S Mamada; K Makino; S Fujishige
        Systems and Human Science - For Safety, Security and Dependability, 2005, Peer-reviewed
      • Generating cut conjunctions and bridge avoiding extensions in graphs
        L Khachiyan; E Boros; K Borys; K Elbassioni; Gurvich, V; K Makino
        ALGORITHMS AND COMPUTATION, 2005, Peer-reviewed
      • Minimizing a monotone concave function with laminar covering constraints
        M Sakashita; K Makino; S Fujishige
        ALGORITHMS AND COMPUTATION, 2005, Peer-reviewed
      • Dual-bounded generating problems: weighted transversals of a hypergraph
        E Boros; VA Gurvich; L Khachiyan; K Makino
        DISCRETE APPLIED MATHEMATICS, Aug. 2004, Peer-reviewed
      • Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2
        S Fujishige; K Makino; T Takabatake; K Kashiwabara
        DISCRETE MATHEMATICS, Apr. 2004, Peer-reviewed
      • How to collect balls moving in the euclidean plane
        Yuichi Asahiro; Takashi Horiyama; Kazuhisa Makino; Hirotaka Ono; Toshinori Sakuma; Masafumi Yamashita
        Electronic Notes in Theoretical Computer Science, 16 Feb. 2004, Peer-reviewed
      • On maximal frequent and minimal infrequent sets in binary matrices
        E Boros; Gurvich, V; L Khachiyan; K Makino
        ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, Nov. 2003, Peer-reviewed
      • Finding essential attributes from binary data
        E Boros; T Horiyama; T Ibaraki; K Makino; M Yagiura
        ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, Nov. 2003, Peer-reviewed
      • Source location problem with flow requirements in directed networks
        H Ito; K Makino; K Arata; S Honami; Y Itatsu; S Fujishige
        OPTIMIZATION METHODS & SOFTWARE, Aug. 2003, Peer-reviewed
      • Interior and exterior functions of positive Boolean functions
        K Makino; H Ono; T Ibaraki
        DISCRETE APPLIED MATHEMATICS, Aug. 2003, Peer-reviewed
      • Inferring minimal functional dependencies in Horn and q-Horn theories
        T Ibaraki; A Kogan; K Makino
        ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, Aug. 2003, Peer-reviewed
      • Efficient dualization of O(log n)-term monotone disjunctive normal forms
        K Makino
        DISCRETE APPLIED MATHEMATICS, Mar. 2003, Peer-reviewed
      • New results on monotone dualization and generating hypergraph transversals
        T Eiter; G Gottlob; K Makino
        SIAM JOURNAL ON COMPUTING, 2003, Peer-reviewed
      • Variations on extending partially defined Boolean functions with missing bits
        E Boros; T Ibaraki; K Makino
        INFORMATION AND COMPUTATION, Jan. 2003, Peer-reviewed
      • Max- and min-neighborhood monopolies
        K Makino; M Yamashita; T Kameda
        ALGORITHMICA, Nov. 2002, Peer-reviewed
      • A simple matching algorithm for regular bipartite graphs
        K Makino; T Takabatake; S Fujishige
        INFORMATION PROCESSING LETTERS, Nov. 2002, Peer-reviewed
      • Logical analysis of data with decomposable structures
        H Ono; K Makino; T Ibaraki
        THEORETICAL COMPUTER SCIENCE, Oct. 2002, Peer-reviewed
      • Dual-bounded generating problems: All minimal integer solutions for a monotone system of linear inequalities
        E Boros; K Elbassioni; Gurvich, V; L Khachiyan; K Makino
        SIAM JOURNAL ON COMPUTING, Aug. 2002, Peer-reviewed
      • Recognition and dualization of disguised bidual Horn functions
        T Eiter; T Ibaraki; K Makino
        INFORMATION PROCESSING LETTERS, Jun. 2002, Peer-reviewed
      • Optimal sink location problem for dynamic flows in a tree network
        S Mamada; K Makino; S Fujishige
        IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, May 2002, Peer-reviewed
      • A linear time algorithm for recognizing regular Boolean functions
        K Makino
        JOURNAL OF ALGORITHMS, May 2002, Peer-reviewed
      • Minimum edge ranking spanning trees of threshold graphs
        K Makino; Y Uno; T Ibaraki
        ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2002, Peer-reviewed
      • Decision lists and related Boolean functions
        T Eiter; T Ibaraki; K Makino
        THEORETICAL COMPUTER SCIENCE, Jan. 2002, Peer-reviewed
      • Locating sources to meet flow demands in undirected networks
        K Arata; S Iwata; K Makino; S Fujishige
        JOURNAL OF ALGORITHMS, Jan. 2002, Peer-reviewed
      • On functional dependencies in q-Horn theories
        T Ibaraki; A Kogan; K Makino
        ARTIFICIAL INTELLIGENCE, Sep. 2001, Peer-reviewed
      • Disjunctions of Horn theories and their cores
        T Eiter; T Ibaraki; K Makino
        SIAM JOURNAL ON COMPUTING, Jul. 2001, Peer-reviewed
      • On minimum edge ranking spanning trees
        K Makino; Y Uno; T Ibaraki
        JOURNAL OF ALGORITHMS, Feb. 2001, Peer-reviewed
      • A satisfiability formulation of problems on level graphs
        Bert Randerath; Ewald Speckenmeyer; Endre Boros; Peter Hammer; Alex Kogan; Kazuhisa Makino; Bruno Simeone; Ondrej Cepek
        Electronic Notes in Discrete Mathematics, 2001, Peer-reviewed
      • Transformations on regular nondominated coteries and their applications
        K Makino; T Kameda
        SIAM JOURNAL ON DISCRETE MATHEMATICS, 2001, Peer-reviewed
      • On the difference of Horn theories
        T Eiter; T Ibaraki; K Makino
        JOURNAL OF COMPUTER AND SYSTEM SCIENCES, Dec. 2000, Peer-reviewed
      • Minimum self-dual decompositions of positive dual-minor Boolean functions
        JC Bioch; T Ibaraki; K Makino
        DISCRETE APPLIED MATHEMATICS, Oct. 1999, Peer-reviewed
      • Bidual Horn functions and extensions
        T Eiter; T Ibaraki; K Makino
        DISCRETE APPLIED MATHEMATICS, Oct. 1999, Peer-reviewed
      • Horn extensions of a partially defined Boolean function
        K Makino; K Hatanaka; T Ibaraki
        SIAM JOURNAL ON COMPUTING, Aug. 1999, Peer-reviewed
      • Functional dependencies in Horn theories
        T Ibaraki; A Kogan; K Makino
        ARTIFICIAL INTELLIGENCE, Mar. 1999, Peer-reviewed
      • Logical analysis of binary data with missing bits
        E Boros; T Ibaraki; K Makino
        ARTIFICIAL INTELLIGENCE, Feb. 1999, Peer-reviewed
      • Computing intersections of horn theories for reasoning with models
        T Eiter; T Ibaraki; K Makino
        FIFTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-98) AND TENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICAL INTELLIGENCE (IAAI-98) - PROCEEDINGS, 1998, Peer-reviewed
      • Double Horn functions
        T Eiter; T Ibaraki; K Makino
        INFORMATION AND COMPUTATION, Aug. 1998, Peer-reviewed
      • A fast and simple algorithm for identifying 2-monotonic positive Boolean functions
        K Makino; T Ibaraki
        JOURNAL OF ALGORITHMS, Feb. 1998, Peer-reviewed
      • On disguised double horn functions and extensions
        T Eiter; T Ibaraki; K Makino
        STACS 98 - 15TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, 1998, Peer-reviewed
      • The maximum latency and identification of positive Boolean functions
        K Makino; T Ibaraki
        SIAM JOURNAL ON COMPUTING, Oct. 1997, Peer-reviewed
      • Positive and Horn decomposability of partially defined Boolean functions
        K Makino; K Yano; T Ibaraki
        DISCRETE APPLIED MATHEMATICS, May 1997, Peer-reviewed
      • Interior and exterior functions of Boolean functions
        K Makino; T Ibaraki
        DISCRETE APPLIED MATHEMATICS, Aug. 1996, Peer-reviewed

      Misc.

      • Guest Editors' Foreword
        Khaled Elbassioni; Kazuhisa Makino
        ALGORITHMICA, Nov. 2017
      • Optimal Matroid Partitioning Problems.
        Yasushi Kawase; Kei Kimura; Kazuhisa Makino; Hanna Sumita
        CoRR, 2017, Peer-reviewed
      • RA-002 On the Complexity of finding Optimal Composition Orderings for Piecewise Linear Functions
        Kawase Yasushi; Makino Kazuhisa; Seimi Kento
        情報科学技術フォーラム講演論文集, 24 Aug. 2015
      • 無秩序の代償と安定性の代償 (特集 はじめようゲーム理論)
        河瀬 康志; 牧野 和久
        オペレーションズ・リサーチ, Jun. 2015
      • 1-B-13 線形相補性問題のパラメータ化計算量(学生セッション:離散最適化(3))
        澄田 範奈; 垣村 尚徳; 牧野 和久
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 26 Mar. 2015
      • DS-1-13 Parameterized Complexity of the Linear Complementarity Problem
        Sumita Hanna; Kakimura Naonori; Makino Kazuhisa
        Proceedings of the IEICE General Conference, 24 Feb. 2015
      • 1-C-11 方向つき線形相補性問題の計算複雑度(離散最適化(3))
        澄田 範奈; 垣村 尚徳; 牧野 和久
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 28 Aug. 2014
      • 2-C-6 重みに上下限をもつ比例コスト買い戻し問題(離散最適化(5))
        河瀬 康志; HAN Xin; 牧野 和久
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 28 Aug. 2014
      • 制約充足問題に対する線形固定可能割当ての解析
        木村慧; 牧野和久
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 06 Mar. 2014
      • 1-G-10 線形相補性問題の完全双対整数性(離散最適化(2))
        澄田 範奈; 垣村 尚徳; 牧野 和久
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 06 Mar. 2014
      • 1-G-8 最適合成順問題(離散最適化(1))
        河瀬 康志; 牧野 和久; 勢見 賢人
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 06 Mar. 2014
      • 制約充足問題に対する線形固定可能割当ての解析
        木村慧; 牧野和久
        電子情報通信学会大会講演論文集(CD-ROM), 04 Mar. 2014
      • DS-1-4 On Total Dual Integrality of the Linear Complementarity Problem
        Sumita Hanna; Kakimura Naonori; Makino Kazuhisa
        Proceedings of the IEICE General Conference, 04 Mar. 2014
      • DS-1-2 Optimal Composition Ordering Problems
        Kawase Yasushi; Makino Kazuhisa; Seimi Kento
        Proceedings of the IEICE General Conference, 04 Mar. 2014
      • Randomized Algorithms for Online Knapsack Problems
        Han Xin; Kawase Yasushi; Makino Kazuhisa
        Mathematical Systems Science and its Applications : IEICE technical report, 06 Nov. 2013
      • Randomized Algorithms for Online Knapsack Problems
        Xin Han; Yasushi Kawase; Kazuhisa Makino
        IPSJ SIG Notes, 30 Oct. 2013
      • 2-F-4 オンラインナップサック問題に対する乱択アルゴリズム(離散最適化(5))
        HAN Xin; 河瀬 康志; 牧野 和久
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 11 Sep. 2013
      • A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions
        BOROS Endre; ELBASSIONI Khaled; GURVICH Vladimir; MAKINO Kazuhisa
        IEICE technical report. Theoretical foundations of Computing, 27 Aug. 2013
      • DS-1-7 Online Unweighted Knapsack Problem with Removal Cost
        Xin Han; Kawase Yasushi; Makino Kazuhisa
        Proceedings of the IEICE General Conference, 05 Mar. 2013
      • 整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標
        木村慧; 牧野和久
        電子情報通信学会大会講演論文集, 05 Mar. 2013
      • DS-1-8 Combinatorial Algorithms for Sparse Linear Complementarity Problems
        Sumita Hanna; Kakimura Naonori; Makino Kazuhisa
        Proceedings of the IEICE General Conference, 05 Mar. 2013
      • 1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))
        澄田 範奈; 垣村 尚徳; 牧野 和久
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 12 Sep. 2012
      • 1-C-8 キャンセルコスト付きオンラインナップサック問題(離散最適化(1))
        HAN Xin; 河瀬 康志; 牧野 和久
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 12 Sep. 2012
      • 整数線形システムの実行可能性問題に対する計算複雑さの指標
        木村慧; 牧野和久
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 13 Sep. 2011
      • 2-I-3 ネットワークデザインゲームにおけるポテンシャル最小化(離散最適化(3))
        河瀬 康志; 牧野 和久
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 13 Sep. 2011
      • 2-A-11 ロバスト独立システム(離散最適化(3))
        垣村 尚徳; 牧野 和久
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 17 Mar. 2011
      • Online Knapsack Problems with Limited Cuts
        HAN XIN; MAKINO KAZUHISA
        研究報告アルゴリズム（AL）, 19 Jan. 2010
      • Posi-modular Systems with Modulotone Requirements under Permutation Constraints
        ISHII TOSHIMASA; MAKINO KAZUHISA
        研究報告アルゴリズム（AL）, 20 Nov. 2009
      • Deductive Inference for the Interiors and Exteriors of Horn Theories
        MAKINO Kazuhisa; ONO Hirotaka
        IEICE technical report, 29 Jun. 2007
      • Approximation Algorithms for Source Location Problems with Flow Requirements
        SAKASHITA Mariko; MAKINO Kazuhisa; FUJISHIGE Satoru
        IEICE technical report. Theoretical foundations of Computing, 17 Jun. 2005
      • Systems and Human Science - For Safety, Security and Dependability
        Tatsuo Arai; Shigeru Yamamoto; Kazuhisa Makino
        Systems and Human Science - For Safety, Security and Dependability, 2005
      • 木構造動的ネットワークにおける複数個の施設配置問題(組合せ最適化(5))
        間々田 聡子; 宇野 毅明; 牧野 和久; 藤重 悟
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 08 Sep. 2004
      • 無向ネットワーク中のソース配置問題の強NP困難性とその近似アルゴリズム(組合せ最適化(5))
        坂下 麻里子; 牧野 和久; 藤重 悟
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 08 Sep. 2004
      • LA-002 An Approximation Algorithm for a Source Location Problem in Undirected Networks
        Sakashita Mariko; Makino Kazuhisa; Fujishige Satoru
        情報科学技術レターズ, 20 Aug. 2004
      • ラミナー被覆制約を持つ単調凹関数最小化問題(グラフ・ネットワーク)
        坂下 麻里子; 牧野 和久; 藤重 悟
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 17 Mar. 2004
      • 木構造動的ネットワークにおける複数の施設への避難誘導問題(数理計画関連・数理モデル)
        間々田 聡子; 牧野 和久; 藤重 悟
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 17 Mar. 2004
      • Minimizing a Monotone Concave Function with Laminar Covering Constraints
        SAKASHITA Mariko; MAKINO Kazuhisa; FUJISHIGE Satoru
        IPSJ SIG Notes, 30 Jan. 2004
      • Dual - Bounded Generating Problems : An Intersection Inequality for Discrete Distributions and Its Applications
        BOROS Endre; ELBASSIONI Khaled; GURVICH Vladimir; KHACHIYAN Leonid; MAKINO Kazuhisa
        IPSJ SIG Notes, 07 Nov. 2003
      • An O(nlog^2n)Algorithm for the Optimal Sink Lacation Problem on Dynamic Tree Networks
        MAMADA Satoko; UNO Takeshi; MAKINO Kazuhisa; FUJISHIGE Satoru
        日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 10 Sep. 2003
      • Busy Outfielder Problem (New Aspects of Theoretical Computer Science)
        Sakuma Toshinori; Ono Hirotaka; Yamashita Masafumi; Asahiro Yuichi; Makino Kazuhisa; Horiyama Takashi
        RIMS Kokyuroku, May 2003
        Access this misc :
      • New Results on Monotone Dualization and Generating Hypergraph Transversals
        EITER Thomas; GOTTLOB Georg; MAKINO Kazuhisa
        IPSJ SIG Notes, 20 Jan. 2003
      • Minimum edge ranking spanning trees of threshold graphs
        MAKINO Kazuhisa; UNO Yushi; IBARAKI Toshihide
        IEICE technical report. Theoretical foundations of Computing, 17 Oct. 2002
      • All Minimal Integer Solutions for a Monotone System of Linear Inequalities
        BOROS Endre; ELBASSIONI Khaled; GURVICH Vladimir; KHACHIYAN Leonid; MAKINO Kazuhisa
        IPSJ SIG Notes, 18 May 2001
      • On minimum edge ranking spanning trees
        MAKINO Kazuhisa; UNO Yushi; IBARAKI Toshihide
        IPSJ SIG Notes, 08 Nov. 1999
      • データの論理的解析における階層的分解構造について(数理計画(1))
        小野 廣隆; 牧野 和久; 茨木 俊秀
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 23 Mar. 1999
      • データの論理的解析における分解構造について(情報・通信)
        小野 廣隆; 牧野 和久; 茨木 俊秀
        日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 27 May 1998
      • A hierarchial decomposability in logical data analysis
        小野 廣隆; 牧野 和久; 茨木 俊秀
        全国大会講演論文集, 24 Sep. 1997
      • Positive and Horn Decomposability of Partially Defined Boolean Functions
        MAKINO Kazuhisa; YANO Koji; IBARAKI Toshihide
        IEICE technical report. Theoretical foundations of Computing, 22 Jun. 1995
      • The Maximum Latency of Partially Defined Positive Boolean Functions
        MAKINO Kazuhisa; IBARAKI Toshihide
        The Transactions of the Institute of Electronics,Information and Communication Engineers., 25 Aug. 1993
      • 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), 2012, Peer-reviewed
      • Source Location Problems with Flow Requirements
        Kazuhisa Makino
        2012 THIRD INTERNATIONAL CONFERENCE ON NETWORKING AND COMPUTING (ICNC 2012), 2012, Peer-reviewed
      • Interactive regret minimization
        Danupon Nanongkai; Ashwin Lall; Atish Das Sarma; Kazuhisa Makino
        Proceedings of the ACM SIGMOD International Conference on Management of Data, 2012, Peer-reviewed
      • Augmenting edge-connectivity between vertex subsets
        T. Ishii; K. Makino
        Conferences in Research and Practice in Information Technology Series, 2009, Peer-reviewed
      • Finding intersections of bichromatic segments defined by points
        A. Elmasry; K. Makino
        CCCG 2007 - 19th Canadian Conference on Computational Geometry, 2007, Peer-reviewed
      • Evacuation problems and dynamic network flows
        S Mamada; K Makino; S Fujishige
        SICE 2004 ANNUAL CONFERENCE, VOLS 1-3, 2004, Peer-reviewed
      • On computing all abductive explanations
        T Eiter; K Makino
        EIGHTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-02)/FOURTEENTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE (IAAI-02), PROCEEDINGS, 2002, Peer-reviewed

      Books and Other Publications

      • Finding essential attributes in binary data(共著)
        IDEAL 2000, LNCS 1983, 2000, Not refereed
      • Fully consistent extensions of partially defined Boolean functions with missing bits(共著)
        IFIP TCS2000, LNCS 1872, 2000, Not refereed
      • Logical analysis of data with decomposable structures(共著)
        COCOON 2000, LNCS 1858, 2000, Not refereed
      • Locating sources to meet flow demands in undirected networks(共著)
        SWAT 2000, LNCS 1851, 2000, Not refereed
      • Max-and Min-neighborhood monopolies(共著)
        SWAT2000, LNCS 1851, 2000, Not refereed
      • Efficient generation of all regular non-dominated coteries(共著)
        Proceedings of PODC2000, 2000, Not refereed
      • A linear time algorithm for recognizing regular Boolean functions
        ISAAC'99 , LNCS, 1999, Not refereed
      • On minimum edge ranking spanning trees (共著)
        MFCS'99 . LNCS, 1999, Not refereed
      • Interior and exterior functions of positive Booleam functions(共著)
        Proceedings of the 1st Japanese-Hungastan Symposium on Discrete Mathematics and Its applications, 1999, Not refereed
      • On the difference of Horn theories(共著)
        STACS '99 LNCS, 1999, Not refereed
      • Disjunctions of Horn theories and their cores(共著)
        Algorithms and Computation ISAAC '98 LNCS, 1998, Not refereed
      • Computing intersections of Horn theories for reasoning with models(共著)
        Proceedings of AAAI98, 1998, Not refereed
      • On disguised double how functions and extensions(共著)
        STACS '98 LNCS, 1997, Not refereed
      • Two-face Horn extensions(共著)
        Algorithms and Computation ISAAC'97 LNCS, 1997, Not refereed
      • Monotone extensions of Booleam data(共著)
        LNAI Algorithmic Learning Theory ALT'97, 1997, Not refereed
      • Data analysis by positive decision trees(共著)
        Proceedings of International Symposium on cooperative Database Systems for advanced applications, 1996, Not refereed
      • Boolean analysis of imcomplete examples(共著)
        Algorithm Theory-SWAT'96, LNCS 1097, springer, 1996, Not refereed
      • A fast and simple algorithm for identifying 2-monotonic positive functions(共著)
        Algorithms and Computation LNCS1004, Srpringer, 1995, Not refereed
      • The Maximum latency and Identification of positive Boolean Fanctions(共著)
        Algorithms and Computation, LNCS 834, Springer, 1994, Not refereed

      Awards

      • 20 Apr. 2022
        令和4年度 科学技術分野の文部科学大臣表彰 科学技術賞(研究部門)

      External funds: Kakenhi

      • アルゴリズム基礎理論の追究・発展
        Grant-in-Aid for Transformative Research Areas (A)
        Transformative Research Areas, Section (IV)
        Kyoto University
        牧野 和久
        From 19 Nov. 2020, To 31 Mar. 2025, Granted
        アルゴリズム;アルゴリズム論;データ構造
        https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05967/
      • Research Initiatives on Algorithmic Foundations for Social Advancement
        Grant-in-Aid for Transformative Research Areas (A)
        Transformative Research Areas, Section (IV)
        Kyoto University
        湊 真一
        From 19 Nov. 2020, To 31 Mar. 2025, Granted
        革新的アルゴリズム基盤;組織運営;研究推進
        https://kaken.nii.ac.jp/grant/KAKENHI-ORGANIZER-20H05961/
      • Creation of Incentive Design Science
        Grant-in-Aid for Scientific Research (A)
        Medium-sized Section 61:Human informatics and related fields
        Kyushu University
        横尾 真
        From 01 Apr. 2020, To 31 Mar. 2023, Granted
        ゲーム理論;人工知能;最適化;機械学習;実験経済学
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20H00609/
      • 局所構造を利用した高速なアルゴリズムの開発
        Grant-in-Aid for Challenging Research (Exploratory)
        Medium-sized Section 60:Information science, computer engineering, and related fields
        Kyoto University
        牧野 和久
        From 28 Jun. 2019, To 31 Mar. 2024, Granted
        アルゴリズム;アルゴリズム論;主双対法;オンライン問題
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19K22841/
      • Exploring the Limits of Computation
        Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
        Tokyo Institute of Technology
        渡辺 治
        From 01 Apr. 2017, To 31 Mar. 2018, Project Closed
        計算限界解明;研究成果とりまとめ;計算限界;成果のとりまとめ;若手育成;啓発活動
        https://kaken.nii.ac.jp/grant/KAKENHI-WRAPUP-17H06074/
      • Development of efficient algorithms based on enumeration structures
        Grant-in-Aid for Scientific Research (B)
        Kyoto University
        Kazuhisa Makino
        From 01 Apr. 2014, To 31 Mar. 2020, Project Closed
        アルゴリズム;離散数学;最適化;アルゴリズム論;組合せゲーム;正モジュラ;固定パラメータ容易
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-26280001/
      • Developments of discrete optimization theory and efficient algorithms based on submodular structures
        Grant-in-Aid for Scientific Research (B)
        Kyoto University
        Satoru Fujishige
        From 01 Apr. 2013, To 31 Mar. 2019, Project Closed
        離散最適化;組合せ最適化;劣モジュラ関数;離散アルゴリズム;アルゴリズム;劣モジュラ構造;数理計画
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-25280004/
      • Exploring the limits of computation from mathematical logic
        Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
        Science and Engineering
        Kyoto University
        Kazuhisa Makino
        From 28 Jun. 2012, To 31 Mar. 2017, Project Closed
        computation;計算量;反マトロイド;回路計算量;実数計算量;計算複雑度
        https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-24106002/
      • A Multifaced Approach Toward Understanding the Limitations of Compuation
        Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
        Science and Engineering
        Tokyo Institute of Technology
        Osamu Watanabe
        From 28 Jun. 2012, To 31 Mar. 2017, Project Closed
        計算限界解明;研究連携促進;研究拠点形成;若手研究者の育成;成果の総括;成果の波及;計算複雑さの理論;アルゴリズム理論;計算量上下界解析;成果の総括と公表;計算限界解明手法の開拓;多視点からの連携研究;国際研究者交流;各種啓発・研究成果波及;若手研究者育成;多視点からの統合的解析;計算限界研究センター;計算理論若手研究者育成;ELC 秋学校;ELC Seminar;ELC Workshop
        https://kaken.nii.ac.jp/grant/KAKENHI-ORGANIZER-24106001/
      • Deterministic Random Walk
        Grant-in-Aid for Challenging Exploratory Research
        Kyushu University
        Shuji KIJIMA
        From 01 Apr. 2012, To 31 Mar. 2013, Project Closed
        アルゴリズム理論;マルコフ連鎖;脱乱択化
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23650007/
      • Basic studies on discrete enumeration algorithms
        Grant-in-Aid for Scientific Research (C)
        Kyoto University;The University of Tokyo
        Kazuhisa MAKINO
        From 01 Apr. 2010, To 31 Mar. 2015, Project Closed
        列挙;アルゴリズム論;アルゴリズム
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22500007/
      • Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures
        Grant-in-Aid for Scientific Research (B)
        Kyoto University
        Satoru FUJISHIGE
        From 01 Apr. 2008, To 31 Mar. 2013, Project Closed
        OR;離散最適化;アルゴリズム;劣モジュラ関数;組合せ最適化;数理計画;細合せ最滴化
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20310088/
      • Studies on algorithms for large-scale discrete generation problems
        Grant-in-Aid for Young Scientists (A)
        The University of Tokyo
        Kazuhisa MAKINO
        From 01 Apr. 2006, To 31 Mar. 2009, Project Closed
        アルゴリズム;列挙;ネットワーク;信頼性;双対性判定;マトロイド
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18680002/
      • Analysis of Large-scale Discrete Optimization Problems and Development of Efficient Algorithms Based on Submodularity Structures
        Grant-in-Aid for Scientific Research (B)
        Kyoto University
        Satoru FUJISHIGE
        From 01 Apr. 2004, To 31 Mar. 2008, Project Closed
        離散最適化;アルゴリズム;劣モジュラ関数;組合せ最適化;数理計画, Discrete Optimization;Algorithms;Submodular Functions;Combinatorial Optimization;Mathematical Programming
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16310111/
      • ブール理論に基づく離散システムの構造解析と計算限界の研究
        Grant-in-Aid for Scientific Research on Priority Areas
        Science and Engineering
        The University of Tokyo;Osaka University
        牧野 和久
        From 01 Apr. 2004, To 31 Mar. 2008, Project Closed
        アルゴリズム;離散構造;フロー;辺ランキング;施設配置問題;ソース配置問題;連結度;ラミナー;計算量;近似;ポリベーシック多面体;近似アルゴリズム;強NP困難;一般化フロー
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16092217/
      • 離散構造を有する列挙問題の解法に関する研究
        Grant-in-Aid for Young Scientists (B)
        The University of Tokyo;Osaka University
        牧野 和久
        From 01 Apr. 2003, To 31 Mar. 2006, Project Closed
        列挙;マトロイド;計算量;カット;橋;閉路;列挙アルゴリズム;クリーク列挙;双対化問題;重みつき横断;アルゴリズム;準多項式時間;列挙問題;仮設推論
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15700013/
      • ネットワークフロー問題に対する高速かつ実用的アルゴリズムに関する研究
        Grant-in-Aid for Young Scientists (B)
        Osaka University
        牧野 和久
        From 01 Apr. 2001, To 31 Mar. 2003, Project Closed
        施設配置問題;モノポリー;マッチング;仮説推論;多項式時間アルゴリズム;ネットワークフロー;2部マッチング
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780229/
      • Fundamental Research on Fast Algorithms for Large-Scale Discrete Optimization Problems Based on Submodularity Structures
        Grant-in-Aid for Scientific Research (B)
        KYOTO UNIVERSITY;Osaka University
        Satoru FUJISHIGE
        From 01 Apr. 2001, To 31 Mar. 2004, Project Closed
        アルゴリズム;離散最適化;組合せ最適化;劣モジュラ関数;大規模システム, Algorithms;Discrete Optimization;Combinatorial Optimization;Submodular Functions;Large-Seal Systems
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13480113/
      • 現実データからの知識獲得問題に対するブール関数的アプローチ
        Grant-in-Aid for Encouragement of Young Scientists (A)
        Osaka University
        牧野 和久
        From 01 Apr. 1999, To 31 Mar. 2001, Project Closed
        データマイニング;知識表現;推論;ホーンブール関数;部分定義論理関数;論理関数;拡大;ホーン理論;推論問題;データ分析
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11750059/
      • Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures
        Grant-in-Aid for Scientific Research on Priority Areas (B)
        Osaka University
        Satoru FUJISHIGE
        From 01 Apr. 1998, To 31 Mar. 2001, Project Closed
        アルゴリズム;離散最適化;組合せ最適化;劣モジュラ関数;ハイパーグラフ;計算効率;ネットワーク最適化;コテリ理論, Algorithms;Discrete Optimization;Combinatorial Optimization;Submodular Functions;Hypergraphs
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205217/
      • Studies on combinatorial algorithms as problem solving engine
        Grant-in-Aid for Scientific Research (A)
        KYOTO UNIVERSITY
        Toshihide IBARAKI
        From 01 Apr. 1996, To 31 Mar. 1999, Project Closed
        問題解決エンジン;メタヒューリスティクス;CSP(制約充足問題);組合せ最適化;組合せアルゴリズム;タブ-探索;制約充足問題;一般化割当問題;問題解決;組合セアルゴリズム;メタ・ヒューリスティックス, problem solving engine;metaheuristics;CSP (constraint satisfaction problem);combinatorial optimization
        https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08405030/
      list
        Last Updated :2025/05/02

        Education

        Teaching subject(s)

        • From 01 Apr. 2024, To 31 Mar. 2025
          Special study course (Mathematical Science)
          5140, Year-long, Faculty of Science, 12
        • From 01 Apr. 2024, To 31 Mar. 2025
          Seminar on Discrete Optimization b
          1294, Fall, Graduate School of Science, 3
        • From 01 Apr. 2024, To 31 Mar. 2025
          Seminar on Discrete Optimization a
          1293, Spring, Graduate School of Science, 3
        • From 01 Apr. 2024, To 31 Mar. 2025
          Seminar on Discrete Optimization c
          1295, Spring, Graduate School of Science, 3
        • From 01 Apr. 2024, To 31 Mar. 2025
          Seminar on Discrete Optimization d
          1296, Fall, Graduate School of Science, 3
        • From 01 Apr. 2023, To 31 Mar. 2024
          Special study course (Mathematical Science)
          5140, Year-long, Faculty of Science, 12
        • From 01 Apr. 2023, To 31 Mar. 2024
          Seminar on Discrete Optimization d
          1296, Fall, Graduate School of Science, 3
        • From 01 Apr. 2023, To 31 Mar. 2024
          Seminar on Discrete Optimization c
          1295, Spring, Graduate School of Science, 3
        • From 01 Apr. 2023, To 31 Mar. 2024
          Seminar on Discrete Optimization b
          1294, Fall, Graduate School of Science, 3
        • From 01 Apr. 2023, To 31 Mar. 2024
          Seminar on Discrete Optimization a
          1293, Spring, Graduate School of Science, 3
        • From 01 Apr. 2022, To 31 Mar. 2023
          Seminar on Discrete Optimization b
          1294, Fall, Graduate School of Science, 3
        • From 01 Apr. 2022, To 31 Mar. 2023
          Seminar on Discrete Optimization c
          1295, Spring, Graduate School of Science, 3
        • From 01 Apr. 2022, To 31 Mar. 2023
          Seminar on Discrete Optimization d
          1296, Fall, Graduate School of Science, 3
        • From 01 Apr. 2022, To 31 Mar. 2023
          Seminar on Discrete Optimization a
          1293, Spring, Graduate School of Science, 3
        • From 01 Apr. 2022, To 31 Mar. 2023
          Special study course (Mathematical Science)
          5140, Year-long, Faculty of Science, 12
        • From Apr. 2014, To Mar. 2015
          Mathematics seminary
          Year-long, 理学部
        • From Apr. 2014, To Mar. 2015
          Seminar on Discrete Optimization A
          Spring, 理学研究科
        • From Apr. 2014, To Mar. 2015
          Seminar on Discrete Optimization B
          Fall, 理学研究科
        • From Apr. 2014, To Mar. 2015
          Seminar on Discrete Optimization C
          Spring, 理学研究科
        • From Apr. 2014, To Mar. 2015
          Seminar on Discrete Optimization D
          Fall, 理学研究科
        • From Apr. 2014, To Mar. 2015
          Invitation to Modern Mathematics and Mathematical Sciences
          Spring, 全学共通科目
        • From Apr. 2015, To Mar. 2016
          Mathematics seminary
          Year-long, 理学部
        • From Apr. 2015, To Mar. 2016
          Seminar on Discrete Optimization A
          Spring, 理学研究科
        • From Apr. 2015, To Mar. 2016
          Seminar on Discrete Optimization B
          Fall, 理学研究科
        • From Apr. 2015, To Mar. 2016
          Seminar on Discrete Optimization C
          Spring, 理学研究科
        • From Apr. 2015, To Mar. 2016
          Seminar on Discrete Optimization D
          Fall, 理学研究科
        • From Apr. 2016, To Mar. 2017
          Theory of Discrete Algorithms
          Spring, 情報学研究科
        • From Apr. 2016, To Mar. 2017
          Mathematics seminary
          Year-long, 理学部
        • From Apr. 2016, To Mar. 2017
          Seminar on Discrete Optimization A
          Spring, 理学研究科
        • From Apr. 2016, To Mar. 2017
          Seminar on Discrete Optimization B
          Fall, 理学研究科
        • From Apr. 2016, To Mar. 2017
          Seminar on Discrete Optimization C
          Spring, 理学研究科
        • From Apr. 2016, To Mar. 2017
          Seminar on Discrete Optimization D
          Fall, 理学研究科
        • From Apr. 2016, To Mar. 2017
          Theory of Discrete Algorithms
          Spring, 情報学研究科
        • From Apr. 2017, To Mar. 2018
          Theory of Discrete Algorithms
          Spring, 情報学研究科
        • From Apr. 2017, To Mar. 2018
          Mathematics seminary
          Year-long, 理学部
        • From Apr. 2017, To Mar. 2018
          Seminar on Discrete Optimization A
          Spring, 理学研究科
        • From Apr. 2017, To Mar. 2018
          Seminar on Discrete Optimization B
          Fall, 理学研究科
        • From Apr. 2017, To Mar. 2018
          Seminar on Discrete Optimization C
          Spring, 理学研究科
        • From Apr. 2017, To Mar. 2018
          Seminar on Discrete Optimization D
          Fall, 理学研究科
        • From Apr. 2017, To Mar. 2018
          Theory of Discrete Algorithms
          Spring, 情報学研究科
        • From Apr. 2018, To Mar. 2019
          Mathematics seminary
          Year-long, 理学部
        • From Apr. 2018, To Mar. 2019
          Seminar on Discrete Optimization a
          Spring, 理学研究科
        • From Apr. 2018, To Mar. 2019
          Seminar on Discrete Optimization b
          Fall, 理学研究科
        • From Apr. 2018, To Mar. 2019
          Seminar on Discrete Optimization c
          Spring, 理学研究科
        • From Apr. 2018, To Mar. 2019
          Seminar on Discrete Optimization d
          Fall, 理学研究科
        • From Apr. 2019, To Mar. 2020
          Mathematics seminary
          Year-long, 理学部
        • From Apr. 2019, To Mar. 2020
          Seminar on Discrete Optimization a
          Spring, 理学研究科
        • From Apr. 2019, To Mar. 2020
          Seminar on Discrete Optimization b
          Fall, 理学研究科
        • From Apr. 2019, To Mar. 2020
          Seminar on Discrete Optimization c
          Spring, 理学研究科
        • From Apr. 2019, To Mar. 2020
          Seminar on Discrete Optimization d
          Fall, 理学研究科
        • From Apr. 2020, To Mar. 2021
          Special study course (Mathematical Science)
          Year-long, 理学部
        • From Apr. 2020, To Mar. 2021
          Seminar on Discrete Optimization a
          Spring, 理学研究科
        • From Apr. 2020, To Mar. 2021
          Seminar on Discrete Optimization b
          Fall, 理学研究科
        • From Apr. 2020, To Mar. 2021
          Seminar on Discrete Optimization c
          Spring, 理学研究科
        • From Apr. 2020, To Mar. 2021
          Seminar on Discrete Optimization d
          Fall, 理学研究科
        • From Apr. 2021, To Mar. 2022
          Special study course (Mathematical Science)
          Year-long, 理学部
        • From Apr. 2021, To Mar. 2022
          Seminar on Discrete Optimization a
          Spring, 理学研究科
        • From Apr. 2021, To Mar. 2022
          Seminar on Discrete Optimization b
          Fall, 理学研究科
        • From Apr. 2021, To Mar. 2022
          Seminar on Discrete Optimization c
          Spring, 理学研究科
        • From Apr. 2021, To Mar. 2022
          Seminar on Discrete Optimization d
          Fall, 理学研究科

        Participation in PhD Defense

        • Extension of Additive Valuations to General Valuations on the Existence of EFX
          MAHARA RYOGA, Graduate School of Science, Sub-chief Examiner
          23 Mar. 2023
        • Locally Defined Independence Systems on Graphs
          AMANO YUKI, Graduate School of Science, Chief Examiner
          23 Mar. 2023
        • Planar Realizability via Left and Right Applications
          TOMITA HARUKA, Graduate School of Science, Sub-chief Examiner
          23 Mar. 2023
        • Trace Equivalence and Epistemic Logic to Express Security Properties
          MINAMI KIRAKU, Graduate School of Science, Sub-chief Examiner
          23 Mar. 2022
        • Sheaves of Structures, Heyting-Valued Structures, and a Generalization of ■o■s Theorem
          ARATAKE HISASHI, Graduate School of Science, Sub-chief Examiner
          26 Jul. 2021
        list
          Last Updated :2025/05/02

          Administration

          School management (title, position)

          • From 01 Apr. 2023, To 31 Mar. 2024
            京都大学学際融合教育研究推進センタースーパーグローバルコース数学系ユニット構成員
          • From 01 Apr. 2019, To 31 Mar. 2023
            図書館協議会 協議員
          • From 01 Apr. 2019, To 31 Mar. 2020
            図書館協議会第一特別委員会 委員
          • From 01 Apr. 2020, To 31 Mar. 2021
            図書館協議会第一特別委員会 委員
          • From 01 Apr. 2021, To 31 Mar. 2023
            図書館協議会 協議員
          • From 01 Apr. 2021, To 31 Mar. 2023
            図書館資料整備特別委員会 委員

          Faculty management (title, position)

          • From 01 Apr. 2024, To 31 Mar. 2025
            理学研究科数学・数理解析専攻数理解析系主任（第１代理）
          • From 01 Apr. 2024, To 31 Mar. 2025
            理学研究科会議構成員
          • From 01 Apr. 2023, To 31 Mar. 2024
            数理解析研究所　副所長
          • From 01 Apr. 2023, To 31 Mar. 2024
            予算委員会　委員長
          • From 01 Apr. 2021, To 31 Mar. 2023
            理学研究科数学・数理解析専攻数理解析系主任 第一代理
          • From 01 Apr. 2021, To 31 Mar. 2023
            理学研究科会議構成員
          • From 01 Apr. 2019
            図書委員会　委員長
          • From 01 Apr. 2013, To 31 Mar. 2017
            北部構内学術研究支援室運営委員会　委員
          • From 01 Apr. 2017
            情報セキュリティ委員会　委員

          ページ上部へ戻る