基本情報

協力講座

• 理学研究科, 数学・数理解析専攻 解析数理講座, 教授

所属学協会

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

学位

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

経歴

• 自 1997年, 至 2000年

  大阪大学大学院
• 自 1997年, 至 2000年

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

ID,URL

• J-Global ID

  200901024318809857

• 外部リンク

  http://www-sflab.sys.es.osaka-u.ac.jp/~makino/makino.html

researchmap URL

• https://researchmap.jp/read0051675

研究

研究キーワード

• ゲーム理論
• アルゴリズム論
• 最適化
• 離散数学

研究分野

• 自然科学一般, 応用数学、統計数学
• 情報通信, 計算科学

論文

• Generating clause sequences of a CNF formula

  Kristóf Bérczi; Endre Boros; Ondřej Čepek; Khaled Elbassioni; Petr Kučera; Kazuhisa Makino

  Theoretical Computer Science, 2021年02月08日

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

  Kei Kimura; Kazuhisa Makino

  Ann. Oper. Res., 2026年04月

  
• Scheduling on Identical Machines with Setup Time and Unknown Execution Time.

  Yasushi Kawase; Kazuhisa Makino; Vinh Long Phan; Hanna Sumita

  WADS, 2025年

  
• Towards optimal subsidy bounds for envy-freeable allocations.

  Yasushi Kawase; Kazuhisa Makino; Hanna Sumita; Akihisa Tamura; Makoto Yokoo

  Artif. Intell., 2025年

  
• Reallocation Problems with Minimum Completion Time

  Toshimasa Ishii; Jun Kawahara; Kazuhisa Makino; Hirotaka Ono

  Algorithmica, 2025年05月16日

  
• Fair Ride Allocation on a Line.

  Yuki Amano; Ayumi Igarashi 0001; Yasushi Kawase; Kazuhisa Makino; Hirotaka Ono 0001

  ACM Trans. Economics and Comput., 2025年03月

  
• Popular Arborescences and Their Matroid Generalization.

  Telikepalli Kavitha; Kazuhisa Makino; Ildikó Schlotter; Yu Yokoi

  ACM Trans. Algorithms, 2025年

  
• Arborescences, Colorful Forests, and Popularity.

  Telikepalli Kavitha; Kazuhisa Makino; Ildikó Schlotter; Yu Yokoi

  Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms(SODA), 2024年

  
• 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, 2022年11月

  
• 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, 2021年09月01日

  
• 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, 2019年12月24日

  
• Oracle-based primal-dual algorithms for packing and covering semidefinite programs

  Khaled Elbassioni; Kazuhisa Makino

  Leibniz International Proceedings in Informatics, LIPIcs, 2019年09月01日

  
• 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, 2019年08月01日

  
• Sprague–Grundy function of symmetric hypergraphs

  Endre Boros; Vladimir Gurvich; Nhan Bao Ho; Kazuhisa Makino; Peter Mursic

  Journal of Combinatorial Theory. Series A, 2019年07月01日

  
• A Multiplicative Weight Updates Algorithm for Packing and Covering Semi-infinite Linear Programs

  Khaled Elbassioni; Kazuhisa Makino; Waleed Najy

  Algorithmica, 2019年06月01日

  
• 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, 2024年06月

  
• 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

  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, 2024年03月

  
• 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年

  
• 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, 2021年06月

  
• 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年, 査読有り

  
• Ranking top-k trees in tree-based phylogenetic networks

  Momoko Hayamizu; Kazuhisa Makino

  arXiv:1904.12432 [math.CO], 2019年04月

  
• Total dual integrality of the linear complementarity problem.

  Hanna Sumita; Naonori Kakimura; Kazuhisa Makino

  Annals OR, 2019年, 査読有り

  
• Online Knapsack Problems with a Resource Buffer.

  Xin Han; Yasushi Kawase; Kazuhisa Makino; Haruki Yokomaku

  CoRR, 2019年, 査読有り

  
• 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年, 査読有り

  
• Unit Cost Buyback Problem.

  Yasushi Kawase; Xin Han; Kazuhisa Makino

  Theory Comput. Syst., 2019年, 査読有り

  
• Surrogate optimization for p-norms.

  Yasushi Kawase; Kazuhisa Makino

  Discrete Optimization, 2019年, 査読有り

  
• Proportional Cost Buyback Problem with Weight Bounds

  Yasushi Kawase; Xin Han; Kazuhisa Makino

  Theoretical Computer Science, 2019年, 査読有り

  
• Parameterized Edge Hamiltonicity

  Michael Lampis; Kazuhisa Makino; Valia Mitsou; Yushi Uno

  Discrete Applied Mathematics, 2018年10月

  
• Enumerating vertices of 0/1-Polyhedra associated with 0/1-totally unimodular matrices

  Khaled Elbassioni; Kazuhisa Makino

  Leibniz International Proceedings in Informatics, LIPIcs, 2018年06月01日, 査読有り

  
• Markov decision processes and stochastic games with total effective payoff

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  Annals of Operations Research, 2018年05月28日, 査読有り

  
• On the Sprague–Grundyfunction of EXACTk-NIM

  Endre Boros; Vladimir Gurvich; Nhan Bao Ho; Kazuhisa Makino; Peter Mursic

  Discrete Applied Mathematics, 2018年04月20日, 査読有り

  
• 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, 2018年03月01日, 査読有り

  
• Autark assignments of Horn CNFs

  Kei Kimura; Kazuhisa Makino

  Japan Journal of Industrial and Applied Mathematics, 2018年03月01日, 査読有り

  
• Online knapsack problem under concave functions

  Xin Han; Qinyang Chen; Kazuhisa Makino

  Theoretical Computer Science, 2018年, 査読有り

  
• 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年, 査読有り

  
• Linear Satisfiability Preserving Assignments.

  Kei Kimura; Kazuhisa Makino

  J. Artif. Intell. Res., 2018年, 査読有り

  
• Optimal Composition Ordering Problems for Piecewise Linear Functions.

  Array,Kazuhisa Makino; Kento Seimi

  Algorithmica, 2018年, 査読有り

  
• A convex programming-based algorithm for mean payoff stochastic games with perfect information

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  OPTIMIZATION LETTERS, 2017年12月, 査読有り

  
• 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, 2017年09月19日, 査読有り

  
• Parameterized Complexity of Sparse Linear Complementarity Problems

  Hanna Sumita; Naonori Kakimura; Kazuhisa Makino

  ALGORITHMICA, 2017年09月, 査読有り

  
• A representation of antimatroids by Horn rules and its application to educational systems

  Hiyori Yoshikawa; Hiroshi Hirai; Kazuhisa Makino

  Journal of Mathematical Psychology, 2017年04月01日, 査読有り

  
• A nested family of -total effective rewards for positional games

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  INTERNATIONAL JOURNAL OF GAME THEORY, 2017年03月, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• Optimal composition ordering problems for piecewise linear functions

  Yasushi Kawase; Kazuhisa Makino; Kento Seimi

  Leibniz International Proceedings in Informatics, LIPIcs, 2016年12月01日, 査読有り

  
• 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, 2016年11月, 査読有り

  
• Online minimization knapsack problem

  Xin Han; Kazuhisa Makino

  THEORETICAL COMPUTER SCIENCE, 2016年01月, 査読有り

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

  Kei Kimura; Kazuhisa Makino

  Discrete Applied Mathematics, 2016年, 査読有り

  
• 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年, 査読有り

  
• On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets

  Khaled Elbassioni; Kazuhisa Makino; Kurt Mehlhorn; Fahimeh Ramezani

  ALGORITHMICA, 2015年10月, 査読有り

  
• Deterministic random walks on finite graphs

  Shuji Kijima; Kentaro Koga; Kazuhisa Makino

  RANDOM STRUCTURES & ALGORITHMS, 2015年07月, 査読有り

  
• 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年, 査読有り

  
• Parameterized Algorithms for Parity Games

  Jakub Gajarsky; Michael Lampis; Kazuhisa Makino; Valia Mitsou; Sebastian Ordyniak

  MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT II, 2015年, 査読有り

  
• 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年, 査読有り

  
• The Linear Complementarity Problems with a Few Variables per Constraint.

  Hanna Sumita; Naonori Kakimura; Kazuhisa Makino

  Math. Oper. Res., 2015年, 査読有り

  
• 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年, 査読有り

  
• Parameterized Edge Hamiltonicity

  Michael Lampis; Kazuhisa Makino; Valia Mitsou; Yushi Uno

  GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2014年, 査読有り

  
• 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年, 査読有り

  
• Generating Vertices of Polyhedra and Related Problems of Monotone Generation

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  POLYHEDRAL COMPUTATION, 2009年, 査読有り

  
• New Results for Horn Cores and Envelopes of Horn Disjunctions

  Thomas Eiter; Kazuhisa Makino

  ECAI 2008, PROCEEDINGS, 2008年, 査読有り

  
• 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), 2007年05月, 査読有り

  
• 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年, 査読有り

  
• On the fractional chromatic number of monotone self-dual Boolean functions

  Daya Ram Gaur; Kazuhisa Makino

  FRONTIERS IN ALGORITHMICS, PROCEEDINGS, 2007年, 査読有り

  
• 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年, 査読有り

  
• Minimum transversals in posi-modular systems

  Mariko Sakashita; Kazuhisa Makino; Hiroshi Nagamochi; Satoru Fujishige

  ALGORITHMS - ESA 2006, PROCEEDINGS, 2006年, 査読有り

  
• 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年, 査読有り

  
• New Algorithms for Enumerating All Maximal Cliques

  Kazuhisa Makino; Takeaki Uno

  Lecture Notes in Computer Science (SWAT2004), 2004年07月, 査読有り

  
• 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年, 査読有り

  
• An O(nlog^2n) Algorithm for the Optimal Sink Location Problem on Dynamic Tree Networks

  間々田 聡子; 宇野 毅明; 牧野 和久; 藤重 悟

  第93回情報処理学会アルゴリズム研究会, 2004年01月

  
• The evacuation problem, dynamic network flows, and algorithms

  S Mamada; K Makino; T Takabatake; S Fujishige

  SICE 2003 ANNUAL CONFERENCE, VOLS 1-3, 2003年, 査読有り

  
• 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年, 査読有り

  
• Generating all abductive explanations for queries on propositional horn theories

  T Eiter; K Makino

  COMPUTER SCIENCE LOGIC, PROCEEDINGS, 2003年, 査読有り

  
• Abduction and the dualization problem

  T Eiter; K Makino

  DISCOVERY SCIENCE, PROCEEDINGS, 2003年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph

  B Rutcor; Gurvich, V; L Khachiyan; K Makino

  SIAM JOURNAL ON COMPUTING, 2000年04月, 査読有り

  
• 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年, 査読有り

  
• Generating partial and multiple transversals of a hypergraph

  E Boros; Gurvich, V; L Khachiyan; K Makino

  AUTOMATA LANGUAGES AND PROGRAMMING, 2000年, 査読有り

  
• Max- and min-neighborhood monopolies

  K Makino; M Yamashita; T Kameda

  ALGORITHM THEORY - SWAT 2000, 2000年, 査読有り

  
• Locating sources to meet flow demands in undirected networks

  K Arata; S Iwata; K Makino; S Fujishige

  ALGORITHM THEORY - SWAT 2000, 2000年, 査読有り

  
• Inner-core and outer-core functions of partially defined Boolean functions

  K Makino; T Ibaraki

  DISCRETE APPLIED MATHEMATICS, 1999年10月, 査読有り

  
• Computing intersections of Horn theories for reasoning with models

  T Eiter; T Ibaraki; K Makino

  ARTIFICIAL INTELLIGENCE, 1999年05月, 査読有り

  
• 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年, 査読有り

  
• Data analysis by positive decision trees

  K Makino; T Suda; H Ono; T Ibaraki

  IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1999年01月, 査読有り

  
• 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年, 査読有り

  
• Convexity of Elementary Flow Games.

  永持仁; 牧野和久; ZENG D‐Z; 村田真紀; 茨木俊秀

  電子情報通信学会論文誌 D-1, 1998年06月, 査読有り

  
• Error-free and best-fit extensions of partially defined Boolean functions

  E Bores; T Ibaraki; K Makino

  INFORMATION AND COMPUTATION, 1998年02月, 査読有り

  
• Disjunctions of horn theories and their cores

  T Eiter; T Ibaraki; K Makino

  ALGORITHMS AND COMPUTATIONS, 1998年, 査読有り

  
• Two-face Horn extensions

  T Eiter; T Ibaraki; K Makino

  ALGORITHMS AND COMPUTATION, PROCEEDINGS, 1997年, 査読有り

  
• Monotone extensions of Boolean data sets

  E Boros; T Ibaraki; K Makino

  ALGORITHMIC LEARNING THEORY, 1997年, 査読有り

  
• Markov decision processes and stochastic games with total effective payoff

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  Leibniz International Proceedings in Informatics, LIPIcs, 2015年02月01日, 査読有り

  
• Randomized algorithms for online knapsack problems

  Xin Han; Yasushi Kawase; Kazuhisa Makino

  THEORETICAL COMPUTER SCIENCE, 2015年01月, 査読有り

  
• Online removable knapsack problem under convex function

  Xin Han; Yasushi Kawase; Kazuhisa Makino; He Guo

  THEORETICAL COMPUTER SCIENCE, 2014年06月, 査読有り

  
• Augmenting Edge-Connectivity between Vertex Subsets

  Toshimasa Ishii; Kazuhisa Makino

  ALGORITHMICA, 2014年05月, 査読有り

  
• 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年, 査読有り

  
• Derandomizing the HSSW Algorithm for 3-SAT

  Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto

  ALGORITHMICA, 2013年10月, 査読有り

  
• 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, 2013年07月, 査読有り

  
• On Canonical Forms for Zero-Sum Stochastic Mean Payoff Games

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  DYNAMIC GAMES AND APPLICATIONS, 2013年06月, 査読有り

  
• Nash equilibria with minimum potential in undirected broadcast games

  Yasushi Kawase; Kazuhisa Makino

  THEORETICAL COMPUTER SCIENCE, 2013年04月, 査読有り

  
• Unit Cost Buyback Problem

  Yasushi Kawase; Xin Han; Kazuhisa Makino

  ALGORITHMS AND COMPUTATION, 2013年, 査読有り

  
• ROBUST MATCHINGS AND MATROID INTERSECTIONS

  Ryo Fujita; Yusuke Kobayashi; Kazuhisa Makino

  SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013年, 査読有り

  
• ROBUST INDEPENDENCE SYSTEMS

  Naonori Kakimura; Kazuhisa Makino

  SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• Online Unweighted Knapsack Problem with Removal Cost

  Xin Han; Yasushi Kawase; Kazuhisa Makino

  ALGORITHMICA, 2014年09月, 査読有り

  
• 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年, 査読有り

  
• Deductive Inference for the Interiors and Exteriors of Horn Theories

  Kazuhisa Makino; Hirotaka Ono

  ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2012年08月, 査読有り

  
• 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, 2012年02月, 査読有り

  
• Trichotomy for integer linear systems based on their sign patterns

  Kei Kimura; Kazuhisa Makino

  Leibniz International Proceedings in Informatics, LIPIcs, 2012年, 査読有り

  
• Computing knapsack solutions with cardinality robustness

  Naonori Kakimura; Kazuhisa Makino; Kento Seimi

  JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS, 2012年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS

  Khaled Elbassioni; Amr Elmasry; Kazuhisa Makino

  INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2011年10月, 査読有り

  
• On the readability of monotone Boolean formulae

  Khaled Elbassioni; Kazuhisa Makino; Imran Rauf

  JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011年10月, 査読有り

  
• Nash-solvable two-person symmetric cycle game forms

  Endre Boros; Vladimir Gurvich; Kazuhisa Makino; Wei Shao

  DISCRETE APPLIED MATHEMATICS, 2011年09月, 査読有り

  
• An exact algorithm for the Boolean connectivity problem for k-CNF

  Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto

  THEORETICAL COMPUTER SCIENCE, 2011年08月, 査読有り

  この論文にアクセスする：

  
• Logical analysis of data: classification with justification

  Endre Boros; Yves Crama; Peter L. Hammer; Toshihide Ibaraki; Alexander Kogan; Kazuhisa Makino

  ANNALS OF OPERATIONS RESEARCH, 2011年08月, 査読有り

  
• Computing Knapsack Solutions with Cardinality Robustness

  Naonori Kakimura; Kazuhisa Makino; Kento Seimi

  ALGORITHMS AND COMPUTATION, 2011年, 査読有り

  
• 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年, 査読有り

  
• Robust Independence Systems

  Naonori Kakimura; Kazuhisa Makino

  Automata, Languages and Programming, ICALP, Pt I, 2011年, 査読有り

  
• 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年, 査読有り

  
• Caching Is Hard-Even in the Fault Model

  Marek Chrobak; Gerhard J. Woeginger; Kazuhisa Makino; Haifeng Xu

  ALGORITHMICA, 2012年08月, 査読有り

  
• On the Boolean connectivity problem for Horn relations

  Kazuhisa Makino; Suguru Tamaki; Masaki Yamamoto

  DISCRETE APPLIED MATHEMATICS, 2010年11月, 査読有り

  
• Online removable knapsack with limited cuts

  Xin Han; Kazuhisa Makino

  THEORETICAL COMPUTER SCIENCE, 2010年10月, 査読有り

  
• Acyclic, or totally tight, two-person game forms: Characterization and main properties

  Endre Boros; Vladimir Gurvich; Kazuhisa Makino; David Papp

  DISCRETE MATHEMATICS, 2010年04月, 査読有り

  
• On effectivity functions of game forms

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  GAMES AND ECONOMIC BEHAVIOR, 2010年03月, 査読有り

  
• Robust Matchings and Matroid Intersections

  Ryo Fujita; Yusuke Kobayashi; Kazuhisa Makino

  ALGORITHMS-ESA 2010, PT II, 2010年, 査読有り

  
• Caching Is Hard - Even in the Fault Model

  Marek Chrobak; Gerhard J. Woeginger; Kazuhisa Makino; Haifeng Xu

  ALGORITHMS-ESA 2010, 2010年, 査読有り

  
• LEFT-TO-RIGHT MULTIPLICATION FOR MONOTONE BOOLEAN DUALIZATION

  Endre Boros; Khaled Elbassioni; Kazuhisa Makino

  SIAM JOURNAL ON COMPUTING, 2010年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• Minimal and locally minimal games and game forms

  Endre Boros; Vladimir Gurvich; Kazuhisa Makino

  DISCRETE MATHEMATICS, 2009年07月, 査読有り

  
• On the fractional chromatic number of monotone self-dual Boolean functions

  Daya Ram Gaur; Kazuhisa Makino

  DISCRETE MATHEMATICS, 2009年03月, 査読有り

  
• Online Minimization Knapsack Problem

  Xin Han; Kazuhisa Makino

  APPROXIMATION AND ONLINE ALGORITHMS, 2010年, 査読有り

  
• On the Readability of Monotone Boolean Formulae

  Khaled Elbassioni; Kazuhisa Makino; Imran Rauf

  COMPUTING AND COMBINATORICS, PROCEEDINGS, 2009年, 査読有り

  
• Online Knapsack Problems with Limited Cuts

  Xin Han; Kazuhisa Makino

  ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009年, 査読有り

  
• Posi-modular Systems with Modulotone Requirements under Permutation Constraints

  Toshimasa Ishii; Kazuhisa Makino

  ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009年, 査読有り

  
• MINIMUM TRANSVERSALS IN POSIMODULAR SYSTEMS

  Mariko Sakashita; Kazuhisa Makino; Hiroshi Nagamochi; Satoru Fujishige

  SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009年, 査読有り

  
• A Fast and Simple Parallel Algorithm for the Monotone Duality Problem

  Endre Boros; Kazuhisa Makino

  AUTOMATA, LANGUAGES AND PROGRAMMING, PT I, 2009年, 査読有り

  
• Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs

  Khaled Elbassioni; Kazuhisa Makino; Imran Rauf

  ALGORITHMS - ESA 2009, PROCEEDINGS, 2009年, 査読有り

  
• Generating cut conjunctions in graphs and related problems

  Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  ALGORITHMICA, 2008年07月, 査読有り

  
• Minimizing a monotone concave function with laminar covering constraints

  Mariko Sakashita; Kazuhisa Makino; Satoru Fujishige

  DISCRETE APPLIED MATHEMATICS, 2008年06月, 査読有り

  
• Computational aspects of monotone dualization: A brief survey

  Thomas Eiter; Kazuhisa Makino; Georg Gottlob

  DISCRETE APPLIED MATHEMATICS, 2008年06月, 査読有り

  
• Minimum cost source location problems with flow requirements

  Mariko Sakashita; Kazuhisa Makino; Satoru Fujishige

  ALGORITHMICA, 2008年04月, 査読有り

  
• Deductive Inference for the Interiors and Exteriors of Horn Theories

  Kazuhisa Makino; Hirotaka Ono

  ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2008年, 査読有り

  
• On Berge multiplication for monotone Boolean dualization

  Endre Boros; Khaled Elbassioni; Kazuhisa Makino

  AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, PROCEEDINGS, 2008年, 査読有り

  
• A complete characterization of nash-solvability of bimatrix games in terms of the exclusion of certain 2×2 subgames

  E. Boros; K. Elbassioni; V. Gurvich; K. Makino; V. Oudalov

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2008年, 査読有り

  
• 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, 2007年12月, 査読有り

  
• 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, 2007年06月, 査読有り

  
• 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, 2007年12月, 査読有り

  
• On computing all abductive explanations from a propositional horn theory

  Thomas Eiter; Kazuhisa Making

  JOURNAL OF THE ACM, 2007年, 査読有り

  
• Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

  Leonid Khachiyan; Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

  DISCRETE APPLIED MATHEMATICS, 2007年01月, 査読有り

  
• 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, 2006年11月, 査読有り

  
• How to collect balls moving in the Euclidean plane

  Yuichi Asahiro; Takashi Horiyama; Kazuhisa Makino; Hirotaka Ono; Toshinori Sakuma; Masafumi Yamashita

  DISCRETE APPLIED MATHEMATICS, 2006年11月, 査読有り

  
• Minimum edge ranking spanning trees of split graphs

  Kazuhisa Makino; Yushi Uno; Toshihide Ibaraki

  DISCRETE APPLIED MATHEMATICS, 2006年11月, 査読有り

  
• Minimum cost source location problems with flow requirements

  M Sakashita; K Makino; S Fujishige

  LATIN 2006: THEORETICAL INFORMATICS, 2006年, 査読有り

  
• 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年, 査読有り

  
• 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, 2005年09月, 査読有り

  
• Special section on discrete mathematics and its applications

  K Makino

  IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2005年05月, 査読有り

  
• Preface

  T. Arai; S. Yamamoto; K. Makino

  Systems and Human Science - For Safety, Security and Dependability, 2005年, 査読有り

  
• 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年, 査読有り

  
• 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年, 査読有り

  
• Minimizing a monotone concave function with laminar covering constraints

  M Sakashita; K Makino; S Fujishige

  ALGORITHMS AND COMPUTATION, 2005年, 査読有り

  
• Dual-bounded generating problems: weighted transversals of a hypergraph

  E Boros; VA Gurvich; L Khachiyan; K Makino

  DISCRETE APPLIED MATHEMATICS, 2004年08月, 査読有り

  
• Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2

  S Fujishige; K Makino; T Takabatake; K Kashiwabara

  DISCRETE MATHEMATICS, 2004年04月, 査読有り

  
• 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, 2004年02月16日, 査読有り

  
• On maximal frequent and minimal infrequent sets in binary matrices

  E Boros; Gurvich, V; L Khachiyan; K Makino

  ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2003年11月, 査読有り

  
• Finding essential attributes from binary data

  E Boros; T Horiyama; T Ibaraki; K Makino; M Yagiura

  ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2003年11月, 査読有り

  
• Source location problem with flow requirements in directed networks

  H Ito; K Makino; K Arata; S Honami; Y Itatsu; S Fujishige

  OPTIMIZATION METHODS & SOFTWARE, 2003年08月, 査読有り

  
• Interior and exterior functions of positive Boolean functions

  K Makino; H Ono; T Ibaraki

  DISCRETE APPLIED MATHEMATICS, 2003年08月, 査読有り

  
• Inferring minimal functional dependencies in Horn and q-Horn theories

  T Ibaraki; A Kogan; K Makino

  ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2003年08月, 査読有り

  
• Efficient dualization of O(log n)-term monotone disjunctive normal forms

  K Makino

  DISCRETE APPLIED MATHEMATICS, 2003年03月, 査読有り

  
• New results on monotone dualization and generating hypergraph transversals

  T Eiter; G Gottlob; K Makino

  SIAM JOURNAL ON COMPUTING, 2003年, 査読有り

  
• Variations on extending partially defined Boolean functions with missing bits

  E Boros; T Ibaraki; K Makino

  INFORMATION AND COMPUTATION, 2003年01月, 査読有り

  
• Max- and min-neighborhood monopolies

  K Makino; M Yamashita; T Kameda

  ALGORITHMICA, 2002年11月, 査読有り

  
• A simple matching algorithm for regular bipartite graphs

  K Makino; T Takabatake; S Fujishige

  INFORMATION PROCESSING LETTERS, 2002年11月, 査読有り

  
• Logical analysis of data with decomposable structures

  H Ono; K Makino; T Ibaraki

  THEORETICAL COMPUTER SCIENCE, 2002年10月, 査読有り

  
• 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, 2002年08月, 査読有り

  
• Recognition and dualization of disguised bidual Horn functions

  T Eiter; T Ibaraki; K Makino

  INFORMATION PROCESSING LETTERS, 2002年06月, 査読有り

  
• 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, 2002年05月, 査読有り

  
• A linear time algorithm for recognizing regular Boolean functions

  K Makino

  JOURNAL OF ALGORITHMS, 2002年05月, 査読有り

  
• Minimum edge ranking spanning trees of threshold graphs

  K Makino; Y Uno; T Ibaraki

  ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2002年, 査読有り

  
• Decision lists and related Boolean functions

  T Eiter; T Ibaraki; K Makino

  THEORETICAL COMPUTER SCIENCE, 2002年01月, 査読有り

  
• Locating sources to meet flow demands in undirected networks

  K Arata; S Iwata; K Makino; S Fujishige

  JOURNAL OF ALGORITHMS, 2002年01月, 査読有り

  
• On functional dependencies in q-Horn theories

  T Ibaraki; A Kogan; K Makino

  ARTIFICIAL INTELLIGENCE, 2001年09月, 査読有り

  
• Disjunctions of Horn theories and their cores

  T Eiter; T Ibaraki; K Makino

  SIAM JOURNAL ON COMPUTING, 2001年07月, 査読有り

  
• On minimum edge ranking spanning trees

  K Makino; Y Uno; T Ibaraki

  JOURNAL OF ALGORITHMS, 2001年02月, 査読有り

  
• 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年, 査読有り

  
• Transformations on regular nondominated coteries and their applications

  K Makino; T Kameda

  SIAM JOURNAL ON DISCRETE MATHEMATICS, 2001年, 査読有り

  
• On the difference of Horn theories

  T Eiter; T Ibaraki; K Makino

  JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000年12月, 査読有り

  
• Minimum self-dual decompositions of positive dual-minor Boolean functions

  JC Bioch; T Ibaraki; K Makino

  DISCRETE APPLIED MATHEMATICS, 1999年10月, 査読有り

  
• Bidual Horn functions and extensions

  T Eiter; T Ibaraki; K Makino

  DISCRETE APPLIED MATHEMATICS, 1999年10月, 査読有り

  
• Horn extensions of a partially defined Boolean function

  K Makino; K Hatanaka; T Ibaraki

  SIAM JOURNAL ON COMPUTING, 1999年08月, 査読有り

  
• Functional dependencies in Horn theories

  T Ibaraki; A Kogan; K Makino

  ARTIFICIAL INTELLIGENCE, 1999年03月, 査読有り

  
• Logical analysis of binary data with missing bits

  E Boros; T Ibaraki; K Makino

  ARTIFICIAL INTELLIGENCE, 1999年02月, 査読有り

  
• 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年, 査読有り

  
• Double Horn functions

  T Eiter; T Ibaraki; K Makino

  INFORMATION AND COMPUTATION, 1998年08月, 査読有り

  
• A fast and simple algorithm for identifying 2-monotonic positive Boolean functions

  K Makino; T Ibaraki

  JOURNAL OF ALGORITHMS, 1998年02月, 査読有り

  
• 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年, 査読有り

  
• The maximum latency and identification of positive Boolean functions

  K Makino; T Ibaraki

  SIAM JOURNAL ON COMPUTING, 1997年10月, 査読有り

  
• Positive and Horn decomposability of partially defined Boolean functions

  K Makino; K Yano; T Ibaraki

  DISCRETE APPLIED MATHEMATICS, 1997年05月, 査読有り

  
• Interior and exterior functions of Boolean functions

  K Makino; T Ibaraki

  DISCRETE APPLIED MATHEMATICS, 1996年08月, 査読有り

  

MISC

• Guest Editors' Foreword

  Khaled Elbassioni; Kazuhisa Makino

  ALGORITHMICA, 2017年11月

  
• Optimal Matroid Partitioning Problems.

  Yasushi Kawase; Kei Kimura; Kazuhisa Makino; Hanna Sumita

  CoRR, 2017年, 査読有り

  
• RA-002 区分線形関数に対する最適合成順問題の計算量(A分野:モデル・アルゴリズム・プログラミング,査読付き論文)

  河瀬 康志; 牧野 和久; 勢見 賢人

  情報科学技術フォーラム講演論文集, 2015年08月24日

  
• 無秩序の代償と安定性の代償 (特集 はじめようゲーム理論)

  河瀬 康志; 牧野 和久

  オペレーションズ・リサーチ, 2015年06月

  
• 1-B-13 線形相補性問題のパラメータ化計算量(学生セッション:離散最適化(3))

  澄田 範奈; 垣村 尚徳; 牧野 和久

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

  
• DS-1-13 線形相補性問題のパラメータ化計算量(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

  澄田 範奈; 垣村 尚徳; 牧野 和久

  電子情報通信学会総合大会講演論文集, 2015年02月24日

  
• 1-C-11 方向つき線形相補性問題の計算複雑度(離散最適化(3))

  澄田 範奈; 垣村 尚徳; 牧野 和久

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

  
• 2-C-6 重みに上下限をもつ比例コスト買い戻し問題(離散最適化(5))

  河瀬 康志; HAN Xin; 牧野 和久

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

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

  木村慧; 牧野和久

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

  
• 1-G-10 線形相補性問題の完全双対整数性(離散最適化(2))

  澄田 範奈; 垣村 尚徳; 牧野 和久

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

  
• 1-G-8 最適合成順問題(離散最適化(1))

  河瀬 康志; 牧野 和久; 勢見 賢人

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

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

  木村慧; 牧野和久

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

  
• DS-1-4 線形相補性問題の完全双対整数性(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

  澄田 範奈; 垣村 尚徳; 牧野 和久

  電子情報通信学会総合大会講演論文集, 2014年03月04日

  
• DS-1-2 最適合成順問題(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

  河瀬 康志; 牧野 和久; 勢見 賢人

  電子情報通信学会総合大会講演論文集, 2014年03月04日

  
• Randomized Algorithms for Online Knapsack Problems (システム数理と応用)

  Han Xin; Kawase Yasushi; Makino Kazuhisa

  電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 2013年11月06日

  
• Randomized Algorithms for Online Knapsack Problems

  Xin Han; Yasushi Kawase; Kazuhisa Makino

  研究報告アルゴリズム（AL）, 2013年10月30日

  
• 2-F-4 オンラインナップサック問題に対する乱択アルゴリズム(離散最適化(5))

  HAN Xin; 河瀬 康志; 牧野 和久

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

  
• 定数個のランダム点をもつ完全情報である二人ゼロ和確率期待ゲームに対する擬多項式時間アルゴリズム(一般)

  BOROS Endre; ELBASSIONI Khaled; GURVICH Vladimir; 牧野 和久

  電子情報通信学会技術研究報告. COMP, コンピュテーション, 2013年08月27日

  
• DS-1-7 キャンセルコスト付きオンライン重みなしナップサック問題(DS-1.COMP学生シンポジウム,シンポジウムセッション)

  Xin Han; 河瀬 康志; 牧野 和久

  電子情報通信学会総合大会講演論文集, 2013年03月05日

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

  木村慧; 牧野和久

  電子情報通信学会大会講演論文集, 2013年03月05日

  
• DS-1-8 疎な線形相補性問題に対する組合せ的アルゴリズム(DS-1.COMP学生シンポジウム,シンポジウムセッション)

  澄田 範奈; 垣村 尚徳; 牧野 和久

  電子情報通信学会総合大会講演論文集, 2013年03月05日

  
• 1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))

  澄田 範奈; 垣村 尚徳; 牧野 和久

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

  
• 1-C-8 キャンセルコスト付きオンラインナップサック問題(離散最適化(1))

  HAN Xin; 河瀬 康志; 牧野 和久

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

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

  木村慧; 牧野和久

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

  
• 2-I-3 ネットワークデザインゲームにおけるポテンシャル最小化(離散最適化(3))

  河瀬 康志; 牧野 和久

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

  
• 2-A-11 ロバスト独立システム(離散最適化(3))

  垣村 尚徳; 牧野 和久

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

  
• Online Knapsack Problems with Limited Cuts

  Xin Han; Kazuhisa Makino

  研究報告アルゴリズム（AL）, 2010年01月19日

  
• 順列制約をみたす模調要求をもつ正モジュラシステムについて

  石井 利昌; 牧野 和久

  研究報告アルゴリズム（AL）, 2009年11月20日

  
• ホーン理論の内包・外包に対する演繹推論

  牧野 和久; 小野 廣隆

  電子情報通信学会技術研究報告. COMP, コンピュテーション, 2007年06月29日

  
• フロー制約を持つソース配置問題に対する近似アルゴリズム

  坂下 麻里子; 牧野 和久; 藤重 悟

  電子情報通信学会技術研究報告. COMP, コンピュテーション, 2005年06月17日

  
• 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))

  間々田 聡子; 宇野 毅明; 牧野 和久; 藤重 悟

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

  
• 無向ネットワーク中のソース配置問題の強NP困難性とその近似アルゴリズム(組合せ最適化(5))

  坂下 麻里子; 牧野 和久; 藤重 悟

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

  
• LA-002 無向ネットワーク中のソース配置問題に対する近似アルゴリズム(A. モデル・アルゴリズム・プログラミング)

  坂下 麻里子; 牧野 和久; 藤重 悟

  情報科学技術レターズ, 2004年08月20日

  
• ラミナー被覆制約を持つ単調凹関数最小化問題(グラフ・ネットワーク)

  坂下 麻里子; 牧野 和久; 藤重 悟

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

  
• 木構造動的ネットワークにおける複数の施設への避難誘導問題(数理計画関連・数理モデル)

  間々田 聡子; 牧野 和久; 藤重 悟

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

  
• ラミナー被覆制約を持つ単調凹関数最小化問題

  坂下 麻里子; 牧野 和久; 藤重 悟

  情報処理学会研究報告アルゴリズム（AL）, 2004年01月30日

  
• 双対制限された列挙問題：離散分布に対する交差不等式とその応用

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Leonid Khachiyan; 牧野 和久

  情報処理学会研究報告アルゴリズム（AL）, 2003年11月07日

  
• An O(nlog^2n)Algorithm for the Optimal Sink Lacation Problem on Dynamic Tree Networks

  間々田 聡子; 宇野 毅; 牧野 和久; 藤重 悟

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

  
• 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)

  佐久間 俊慎; 小野 廣隆; 山下 雅史; 朝廣 雄一; 牧野 和久; 堀山 貴史

  数理解析研究所講究録, 2003年05月

  このMISCにアクセスする：

  
• 単調双対化問題とハイパーグラフ横断列挙問題に対する新しい結果について

  Thomas Eiter; Georg Gottlob; 牧野 和久

  情報処理学会研究報告アルゴリズム（AL）, 2003年01月20日

  
• 閾グラフの最小辺ランキング全域木について

  牧野 和久; 宇野 裕之; 茨木 俊秀

  電子情報通信学会技術研究報告. COMP, コンピュテーション, 2002年10月17日

  
• 単調線形システムにおけるすべての極小な整数解について

  Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Leonid Khachiyan; 牧野 和久

  情報処理学会研究報告アルゴリズム（AL）, 2001年05月18日

  
• 最小辺ランキング全域木問題について

  牧野 和久; 宇野 裕之; 茨木 俊秀

  情報処理学会研究報告アルゴリズム（AL）, 1999年11月08日

  
• データの論理的解析における階層的分解構造について(数理計画(1))

  小野 廣隆; 牧野 和久; 茨木 俊秀

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

  
• データの論理的解析における分解構造について(情報・通信)

  小野 廣隆; 牧野 和久; 茨木 俊秀

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

  
• 論理的データ解析における階層的分解構造について

  小野 廣隆; 牧野 和久; 茨木 俊秀

  全国大会講演論文集, 1997年09月24日

  
• 部分定義論理関数の正論理関数と Horn 関数における関数分解について

  牧野 和久; 矢野 浩仁; 茨木 俊秀

  電子情報通信学会技術研究報告. COMP, コンピュテーション, 1995年06月22日

  
• 不完全に定義された正論理関数の最大潜伏度について

  牧野 和久; 茨木 俊秀

  電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ = The transactions of the Institute of Electronics, Information and Communication Engineers, 1993年08月25日

  
• 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年, 査読有り

  
• Source Location Problems with Flow Requirements

  Kazuhisa Makino

  2012 THIRD INTERNATIONAL CONFERENCE ON NETWORKING AND COMPUTING (ICNC 2012), 2012年, 査読有り

  
• Interactive regret minimization

  Danupon Nanongkai; Ashwin Lall; Atish Das Sarma; Kazuhisa Makino

  Proceedings of the ACM SIGMOD International Conference on Management of Data, 2012年, 査読有り

  
• Augmenting edge-connectivity between vertex subsets

  T. Ishii; K. Makino

  Conferences in Research and Practice in Information Technology Series, 2009年, 査読有り

  
• Finding intersections of bichromatic segments defined by points

  A. Elmasry; K. Makino

  CCCG 2007 - 19th Canadian Conference on Computational Geometry, 2007年, 査読有り

  
• Evacuation problems and dynamic network flows

  S Mamada; K Makino; S Fujishige

  SICE 2004 ANNUAL CONFERENCE, VOLS 1-3, 2004年, 査読有り

  
• 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年, 査読有り

  

書籍等出版物

• Finding essential attributes in binary data(共著)

  IDEAL 2000, LNCS 1983, 2000年, 査読無し

  
• Fully consistent extensions of partially defined Boolean functions with missing bits(共著)

  IFIP TCS2000, LNCS 1872, 2000年, 査読無し

  
• Logical analysis of data with decomposable structures(共著)

  COCOON 2000, LNCS 1858, 2000年, 査読無し

  
• Locating sources to meet flow demands in undirected networks(共著)

  SWAT 2000, LNCS 1851, 2000年, 査読無し

  
• Max-and Min-neighborhood monopolies(共著)

  SWAT2000, LNCS 1851, 2000年, 査読無し

  
• Efficient generation of all regular non-dominated coteries(共著)

  Proceedings of PODC2000, 2000年, 査読無し

  
• A linear time algorithm for recognizing regular Boolean functions

  ISAAC'99 , LNCS, 1999年, 査読無し

  
• On minimum edge ranking spanning trees (共著)

  MFCS'99 . LNCS, 1999年, 査読無し

  
• Interior and exterior functions of positive Booleam functions(共著)

  Proceedings of the 1st Japanese-Hungastan Symposium on Discrete Mathematics and Its applications, 1999年, 査読無し

  
• On the difference of Horn theories(共著)

  STACS '99 LNCS, 1999年, 査読無し

  
• Disjunctions of Horn theories and their cores(共著)

  Algorithms and Computation ISAAC '98 LNCS, 1998年, 査読無し

  
• Computing intersections of Horn theories for reasoning with models(共著)

  Proceedings of AAAI98, 1998年, 査読無し

  
• On disguised double how functions and extensions(共著)

  STACS '98 LNCS, 1997年, 査読無し

  
• Two-face Horn extensions(共著)

  Algorithms and Computation ISAAC'97 LNCS, 1997年, 査読無し

  
• Monotone extensions of Booleam data(共著)

  LNAI Algorithmic Learning Theory ALT'97, 1997年, 査読無し

  
• Data analysis by positive decision trees(共著)

  Proceedings of International Symposium on cooperative Database Systems for advanced applications, 1996年, 査読無し

  
• Boolean analysis of imcomplete examples(共著)

  Algorithm Theory-SWAT'96, LNCS 1097, springer, 1996年, 査読無し

  
• A fast and simple algorithm for identifying 2-monotonic positive functions(共著)

  Algorithms and Computation LNCS1004, Srpringer, 1995年, 査読無し

  
• The Maximum latency and Identification of positive Boolean Fanctions(共著)

  Algorithms and Computation, LNCS 834, Springer, 1994年, 査読無し

  

受賞

• 2022年04月20日

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

外部資金：科学研究費補助金

• アルゴリズム基礎理論の追究・発展

  学術変革領域研究(A)

  学術変革領域研究区分(Ⅳ)

  京都大学

  牧野 和久

  自 2020年11月19日, 至 2025年03月31日, 交付

  アルゴリズム;アルゴリズム論;データ構造

  https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05967/
• 研究領域「革新的アルゴリズム基盤」の組織運営と研究推進

  学術変革領域研究(A)

  学術変革領域研究区分(Ⅳ)

  京都大学

  湊 真一

  自 2020年11月19日, 至 2025年03月31日, 完了

  革新的アルゴリズム基盤;組織運営;アルゴリズム;離散構造処理;社会変革;研究推進

  https://kaken.nii.ac.jp/grant/KAKENHI-ORGANIZER-20H05961/
• インセンティブ設計科学の創出

  基盤研究(A)

  中区分61:人間情報学およびその関連分野

  九州大学

  横尾 真

  自 2020年04月01日, 至 2023年03月31日, 完了

  ゲーム理論;人工知能;最適化;機械学習;実験経済学

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20H00609/
• 局所構造を利用した高速なアルゴリズムの開発

  挑戦的研究(萌芽)

  中区分60:情報科学、情報工学およびその関連分野

  京都大学

  牧野 和久

  自 2019年06月28日, 至 2025年03月31日, 完了

  アルゴリズム;アルゴリズム論;主双対法;オンライン問題

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19K22841/
• 多面的アプローチの統合による計算限界の解明

  新学術領域研究(研究領域提案型)

  東京工業大学

  渡辺 治

  自 2017年04月01日, 至 2018年03月31日, 完了

  計算限界解明;研究成果とりまとめ;計算限界;成果のとりまとめ;若手育成;啓発活動

  https://kaken.nii.ac.jp/grant/KAKENHI-WRAPUP-17H06074/
• 列挙構造を利用した高速アルゴリズム開発

  基盤研究(B)

  京都大学

  牧野 和久

  自 2014年04月01日, 至 2020年03月31日, 完了

  アルゴリズム;離散数学;最適化;アルゴリズム論;組合せゲーム;正モジュラ;固定パラメータ容易

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-26280001/
• 劣モジュラ的な離散構造に注目した最適化基礎理論の展開と高速アルゴリズム開発

  基盤研究(B)

  京都大学

  藤重 悟

  自 2013年04月01日, 至 2019年03月31日, 完了

  離散最適化;組合せ最適化;劣モジュラ関数;離散アルゴリズム;アルゴリズム;劣モジュラ構造;数理計画

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-25280004/
• 数理論理学からの計算限界解析

  新学術領域研究(研究領域提案型)

  理工系

  京都大学

  牧野 和久

  自 2012年06月28日, 至 2017年03月31日, 完了

  computation;計算量;反マトロイド;回路計算量;実数計算量;計算複雑度

  https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-24106002/
• 多面的アプローチの統合による計算限界の解明

  新学術領域研究(研究領域提案型)

  理工系

  東京工業大学

  渡辺 治

  自 2012年06月28日, 至 2017年03月31日, 完了

  計算限界解明;研究連携促進;研究拠点形成;若手研究者の育成;成果の総括;成果の波及;計算複雑さの理論;アルゴリズム理論;計算量上下界解析;成果の総括と公表;計算限界解明手法の開拓;多視点からの連携研究;国際研究者交流;各種啓発・研究成果波及;若手研究者育成;多視点からの統合的解析;計算限界研究センター;計算理論若手研究者育成;ELC 秋学校;ELC Seminar;ELC Workshop

  https://kaken.nii.ac.jp/grant/KAKENHI-ORGANIZER-24106001/
• ランダムウォークの脱乱択化

  挑戦的萌芽研究

  九州大学

  来嶋 秀治

  自 2012年04月01日, 至 2013年03月31日, 完了

  アルゴリズム理論;マルコフ連鎖;脱乱択化

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23650007/
• 離散列挙アルゴリズムの基礎研究

  基盤研究(C)

  京都大学;東京大学

  牧野 和久

  自 2010年04月01日, 至 2015年03月31日, 完了

  列挙;アルゴリズム論;アルゴリズム

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22500007/
• 劣モジュラ的構造に基づく離散最適化基礎理論の展開と高速アルゴリズム開発

  基盤研究(B)

  京都大学

  藤重 悟

  自 2008年04月01日, 至 2013年03月31日, 完了

  OR;離散最適化;アルゴリズム;劣モジュラ関数;組合せ最適化;数理計画;細合せ最滴化

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20310088/
• 大規模な離散列挙問題に対するアルゴリズムの研究

  若手研究(A)

  東京大学

  牧野 和久

  自 2006年04月01日, 至 2009年03月31日, 完了

  アルゴリズム;列挙;ネットワーク;信頼性;双対性判定;マトロイド

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18680002/
• 大規模離散最適化問題の劣モジュラ的構造に基づく解析と高速アルゴリズム開発

  基盤研究(B)

  京都大学

  藤重 悟

  自 2004年04月01日, 至 2008年03月31日, 完了

  離散最適化;アルゴリズム;劣モジュラ関数;組合せ最適化;数理計画, Discrete Optimization;Algorithms;Submodular Functions;Combinatorial Optimization;Mathematical Programming

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16310111/
• ブール理論に基づく離散システムの構造解析と計算限界の研究

  特定領域研究

  理工系

  東京大学;大阪大学

  牧野 和久

  自 2004年04月01日, 至 2008年03月31日, 完了

  アルゴリズム;離散構造;フロー;辺ランキング;施設配置問題;ソース配置問題;連結度;ラミナー;計算量;近似;ポリベーシック多面体;近似アルゴリズム;強NP困難;一般化フロー

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16092217/
• 離散構造を有する列挙問題の解法に関する研究

  若手研究(B)

  東京大学;大阪大学

  牧野 和久

  自 2003年04月01日, 至 2006年03月31日, 完了

  列挙;マトロイド;計算量;カット;橋;閉路;列挙アルゴリズム;クリーク列挙;双対化問題;重みつき横断;アルゴリズム;準多項式時間;列挙問題;仮設推論

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15700013/
• ネットワークフロー問題に対する高速かつ実用的アルゴリズムに関する研究

  若手研究(B)

  大阪大学

  牧野 和久

  自 2001年04月01日, 至 2003年03月31日, 完了

  施設配置問題;モノポリー;マッチング;仮説推論;多項式時間アルゴリズム;ネットワークフロー;2部マッチング

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780229/
• 大規模離散最適化問題に対する劣モジュラ的構造に基づく高速アルゴリズムの基礎研究

  基盤研究(B)

  京都大学;大阪大学

  藤重 悟

  自 2001年04月01日, 至 2004年03月31日, 完了

  アルゴリズム;離散最適化;組合せ最適化;劣モジュラ関数;大規模システム, Algorithms;Discrete Optimization;Combinatorial Optimization;Submodular Functions;Large-Seal Systems

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13480113/
• 現実データからの知識獲得問題に対するブール関数的アプローチ

  奨励研究(A)

  大阪大学

  牧野 和久

  自 1999年04月01日, 至 2001年03月31日, 完了

  データマイニング;知識表現;推論;ホーンブール関数;部分定義論理関数;論理関数;拡大;ホーン理論;推論問題;データ分析

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11750059/
• 離散最適化アルゴリズムの計算効率と離散構造

  特定領域研究(B)

  大阪大学

  藤重 悟

  自 1998年04月01日, 至 2001年03月31日, 完了

  アルゴリズム;離散最適化;組合せ最適化;劣モジュラ関数;ハイパーグラフ;計算効率;ネットワーク最適化;コテリ理論, Algorithms;Discrete Optimization;Combinatorial Optimization;Submodular Functions;Hypergraphs

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205217/
• 問題解決エンジンとしての組合せアルゴリズムに関する研究

  基盤研究(A)

  京都大学

  茨木 俊秀

  自 1996年04月01日, 至 1999年03月31日, 完了

  問題解決エンジン;メタヒューリスティクス;CSP(制約充足問題);組合せ最適化;組合せアルゴリズム;タブ-探索;制約充足問題;一般化割当問題;問題解決;組合セアルゴリズム;メタ・ヒューリスティックス, problem solving engine;metaheuristics;CSP (constraint satisfaction problem);combinatorial optimization

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08405030/

教育

担当科目

• 自 2026年04月01日, 至 2027年03月31日

  現代の数学と数理解析

  N114, 前期, 国際高等教育院, 2
• 自 2026年04月01日, 至 2027年03月31日

  数理科学課題研究

  5140, 通年集中, 理学部, 12
• 自 2026年04月01日, 至 2027年03月31日

  離散最適化セミナー研究ｂ

  1294, 後期, 理学研究科, 3
• 自 2026年04月01日, 至 2027年03月31日

  離散最適化セミナー研究ａ

  1293, 前期, 理学研究科, 3
• 自 2026年04月01日, 至 2027年03月31日

  離散最適化セミナー研究ｄ

  1296, 後期, 理学研究科, 3
• 自 2026年04月01日, 至 2027年03月31日

  離散最適化セミナー研究ｃ

  1295, 前期, 理学研究科, 3
• 自 2025年04月01日, 至 2026年03月31日

  現代の数学と数理解析

  N114, 前期, 国際高等教育院, 2
• 自 2025年04月01日, 至 2026年03月31日

  数理科学課題研究

  5140, 通年集中, 理学部, 12
• 自 2025年04月01日, 至 2026年03月31日

  離散最適化セミナー研究ｂ

  1294, 後期, 理学研究科, 3
• 自 2025年04月01日, 至 2026年03月31日

  離散最適化セミナー研究ａ

  1293, 前期, 理学研究科, 3
• 自 2025年04月01日, 至 2026年03月31日

  離散最適化セミナー研究ｄ

  1296, 後期, 理学研究科, 3
• 自 2025年04月01日, 至 2026年03月31日

  離散最適化セミナー研究ｃ

  1295, 前期, 理学研究科, 3
• 自 2024年04月01日, 至 2025年03月31日

  数理科学課題研究

  5140, 通年集中, 理学部, 12
• 自 2024年04月01日, 至 2025年03月31日

  離散最適化セミナー研究ｂ

  1294, 後期, 理学研究科, 3
• 自 2024年04月01日, 至 2025年03月31日

  離散最適化セミナー研究ａ

  1293, 前期, 理学研究科, 3
• 自 2024年04月01日, 至 2025年03月31日

  離散最適化セミナー研究ｃ

  1295, 前期, 理学研究科, 3
• 自 2024年04月01日, 至 2025年03月31日

  離散最適化セミナー研究ｄ

  1296, 後期, 理学研究科, 3
• 自 2023年04月01日, 至 2024年03月31日

  数理科学課題研究

  5140, 通年集中, 理学部, 12
• 自 2023年04月01日, 至 2024年03月31日

  離散最適化セミナー研究ｄ

  1296, 後期, 理学研究科, 3
• 自 2023年04月01日, 至 2024年03月31日

  離散最適化セミナー研究ｃ

  1295, 前期, 理学研究科, 3
• 自 2023年04月01日, 至 2024年03月31日

  離散最適化セミナー研究ｂ

  1294, 後期, 理学研究科, 3
• 自 2023年04月01日, 至 2024年03月31日

  離散最適化セミナー研究ａ

  1293, 前期, 理学研究科, 3
• 自 2022年04月01日, 至 2023年03月31日

  離散最適化セミナー研究ｂ

  1294, 後期, 理学研究科, 3
• 自 2022年04月01日, 至 2023年03月31日

  離散最適化セミナー研究ｃ

  1295, 前期, 理学研究科, 3
• 自 2022年04月01日, 至 2023年03月31日

  離散最適化セミナー研究ｄ

  1296, 後期, 理学研究科, 3
• 自 2022年04月01日, 至 2023年03月31日

  離散最適化セミナー研究ａ

  1293, 前期, 理学研究科, 3
• 自 2022年04月01日, 至 2023年03月31日

  数理科学課題研究

  5140, 通年集中, 理学部, 12
• 自 2014年04月, 至 2015年03月

  数学講究

  通年, 理学部
• 自 2014年04月, 至 2015年03月

  離散最適化セミナー研究Ａ

  前期, 理学研究科
• 自 2014年04月, 至 2015年03月

  離散最適化セミナー研究Ｂ

  後期, 理学研究科
• 自 2014年04月, 至 2015年03月

  離散最適化セミナー研究Ｃ

  前期, 理学研究科
• 自 2014年04月, 至 2015年03月

  離散最適化セミナー研究Ｄ

  後期, 理学研究科
• 自 2014年04月, 至 2015年03月

  現代の数学と数理解析

  前期, 全学共通科目
• 自 2015年04月, 至 2016年03月

  数学講究

  通年, 理学部
• 自 2015年04月, 至 2016年03月

  離散最適化セミナー研究Ａ

  前期, 理学研究科
• 自 2015年04月, 至 2016年03月

  離散最適化セミナー研究Ｂ

  後期, 理学研究科
• 自 2015年04月, 至 2016年03月

  離散最適化セミナー研究Ｃ

  前期, 理学研究科
• 自 2015年04月, 至 2016年03月

  離散最適化セミナー研究Ｄ

  後期, 理学研究科
• 自 2016年04月, 至 2017年03月

  Theory of Discrete Algorithms

  前期, 情報学研究科
• 自 2016年04月, 至 2017年03月

  数学講究

  通年, 理学部
• 自 2016年04月, 至 2017年03月

  離散最適化セミナー研究Ａ

  前期, 理学研究科
• 自 2016年04月, 至 2017年03月

  離散最適化セミナー研究Ｂ

  後期, 理学研究科
• 自 2016年04月, 至 2017年03月

  離散最適化セミナー研究Ｃ

  前期, 理学研究科
• 自 2016年04月, 至 2017年03月

  離散最適化セミナー研究Ｄ

  後期, 理学研究科
• 自 2016年04月, 至 2017年03月

  離散アルゴリズム理論

  前期, 情報学研究科
• 自 2017年04月, 至 2018年03月

  Theory of Discrete Algorithms

  前期, 情報学研究科
• 自 2017年04月, 至 2018年03月

  数学講究

  通年, 理学部
• 自 2017年04月, 至 2018年03月

  離散最適化セミナー研究Ａ

  前期, 理学研究科
• 自 2017年04月, 至 2018年03月

  離散最適化セミナー研究Ｂ

  後期, 理学研究科
• 自 2017年04月, 至 2018年03月

  離散最適化セミナー研究Ｃ

  前期, 理学研究科
• 自 2017年04月, 至 2018年03月

  離散最適化セミナー研究Ｄ

  後期, 理学研究科
• 自 2017年04月, 至 2018年03月

  離散アルゴリズム理論

  前期, 情報学研究科
• 自 2018年04月, 至 2019年03月

  数学講究

  通年, 理学部
• 自 2018年04月, 至 2019年03月

  離散最適化セミナー研究ａ

  前期, 理学研究科
• 自 2018年04月, 至 2019年03月

  離散最適化セミナー研究ｂ

  後期, 理学研究科
• 自 2018年04月, 至 2019年03月

  離散最適化セミナー研究ｃ

  前期, 理学研究科
• 自 2018年04月, 至 2019年03月

  離散最適化セミナー研究ｄ

  後期, 理学研究科
• 自 2019年04月, 至 2020年03月

  数学講究

  通年, 理学部
• 自 2019年04月, 至 2020年03月

  離散最適化セミナー研究ａ

  前期, 理学研究科
• 自 2019年04月, 至 2020年03月

  離散最適化セミナー研究ｂ

  後期, 理学研究科
• 自 2019年04月, 至 2020年03月

  離散最適化セミナー研究ｃ

  前期, 理学研究科
• 自 2019年04月, 至 2020年03月

  離散最適化セミナー研究ｄ

  後期, 理学研究科
• 自 2020年04月, 至 2021年03月

  数理科学課題研究

  通年, 理学部
• 自 2020年04月, 至 2021年03月

  離散最適化セミナー研究ａ

  前期, 理学研究科
• 自 2020年04月, 至 2021年03月

  離散最適化セミナー研究ｂ

  後期, 理学研究科
• 自 2020年04月, 至 2021年03月

  離散最適化セミナー研究ｃ

  前期, 理学研究科
• 自 2020年04月, 至 2021年03月

  離散最適化セミナー研究ｄ

  後期, 理学研究科
• 自 2021年04月, 至 2022年03月

  数理科学課題研究

  通年集中, 理学部
• 自 2021年04月, 至 2022年03月

  離散最適化セミナー研究ａ

  前期, 理学研究科
• 自 2021年04月, 至 2022年03月

  離散最適化セミナー研究ｂ

  後期, 理学研究科
• 自 2021年04月, 至 2022年03月

  離散最適化セミナー研究ｃ

  前期, 理学研究科
• 自 2021年04月, 至 2022年03月

  離散最適化セミナー研究ｄ

  後期, 理学研究科

博士学位審査

• ASYMPTOTIC STABILITY OF A WIDE CLASS OF STATIONARY SOLUTIONS FOR THE HARTREE AND SCHR■DINGER EQUATIONS FOR INFINITELY MANY PARTICLES（無限粒子系に対するハートリーおよびシュレーディンガー方程式のある広いクラスに属する定常解の漸近安定性）

  波多間　備, 理学研究科, 副査

  2025年09月24日
• On the classification of duality defects in c=2 compact boson CFTs with a discrete group orbifold（中心電荷2のコンパクトボゾンCFTのオービフォールドとそれらの圏論的対称性について）

  古田　悠馬, 理学研究科, 副査

  2025年03月24日
• Extension of Additive Valuations to General Valuations on the Existence of EFX(EFX配分の存在に関する非加法的評価関数への拡張)

  馬原　凌河, 理学研究科, 副査

  2023年03月23日
• Locally Defined Independence Systems on Graphs（グラフ上で局所的に定義される独立性システム）

  天野　雄樹, 理学研究科, 主査

  2023年03月23日
• Planar Realizability via Left and Right Applications（左右の関数適用を用いた平面実現可能性）

  冨田　悠, 理学研究科, 副査

  2023年03月23日
• Trace Equivalence and Epistemic Logic to Express Security Properties （セキュリティ特性を表現するためのトレース等価と認識論理）

  南　規楽, 理学研究科, 副査

  2022年03月23日
• Sheaves of Structures, Heyting-Valued Structures, and a Generalization of ■o■s Theorem（構造の層・Heyting値構造と■o■の定理の一般化）

  荒武　永史, 理学研究科, 副査

  2021年07月26日

大学運営

全学運営(役職等)

• 自 2026年04月01日, 至 2027年03月31日

  数理解析研究所附属計算機構研究施設 施設長
• 自 2023年04月01日, 至 2024年03月31日

  京都大学学際融合教育研究推進センタースーパーグローバルコース数学系ユニット構成員
• 自 2019年04月01日, 至 2023年03月31日

  図書館協議会 協議員
• 自 2019年04月01日, 至 2020年03月31日

  図書館協議会第一特別委員会 委員
• 自 2020年04月01日, 至 2021年03月31日

  図書館協議会第一特別委員会 委員
• 自 2021年04月01日, 至 2023年03月31日

  図書館協議会 協議員
• 自 2021年04月01日, 至 2023年03月31日

  図書館資料整備特別委員会 委員

部局運営(役職等)

• 自 2026年04月01日, 至 2027年03月31日

  数理解析研究所　環境・安全・衛生管理委員会　委員
• 自 2024年04月01日, 至 2027年03月31日

  数理解析研究所　予算委員会　委員
• 自 2026年04月01日, 至 2027年03月31日

  数理解析研究所計算機運営委員会　委員長
• 自 2017年04月01日, 至 2027年03月31日

  数理解析研究所　情報セキュリティ委員会　委員
• 自 2025年04月01日, 至 2026年03月31日

  理学研究科大学院教育教務委員会委員
• 自 2025年04月01日, 至 2025年10月20日

  理学研究科・数理解析専攻連絡会構成員
• 自 2025年04月01日, 至 2025年10月20日

  理学研究科会議構成員
• 自 2025年04月01日, 至 2025年10月20日

  理学研究科数学・数理解析専攻数理解析系主任
• 自 2024年04月01日, 至 2025年03月31日

  理学研究科数学・数理解析専攻数理解析系主任（第１代理）
• 自 2024年04月01日, 至 2025年03月31日

  理学研究科会議構成員
• 自 2023年04月01日, 至 2024年03月31日

  数理解析研究所　人権問題委員会　委員長
• 自 2023年04月01日, 至 2024年03月31日

  数理解析研究所　環境・安全・衛生管理委員会　委員
• 自 2023年04月01日, 至 2024年03月31日

  数理解析研究所　省エネルギー推進委員会　委員
• 自 2023年04月01日, 至 2024年03月31日

  数理解析研究所　建物・施設整備委員会　委員長
• 自 2023年04月01日, 至 2024年03月31日

  数理解析研究所　副所長
• 自 2023年04月01日, 至 2024年03月31日

  予算委員会　委員長
• 自 2021年04月01日, 至 2023年03月31日

  理学研究科数学・数理解析専攻数理解析系主任 第一代理
• 自 2021年04月01日, 至 2023年03月31日

  理学研究科会議構成員
• 自 2019年04月01日, 至 2023年03月31日

  図書委員会　委員長
• 自 2013年04月01日, 至 2017年03月31日

  北部構内学術研究支援室運営委員会　委員