Makino Kazuhisa 牧野和久

… Alternative Names

Researcher Number	60294162
Other IDs
External Links
Affiliation (Current)	2019: 京都大学, 数理解析研究所, 教授
Affiliation (based on the past Project Information) *help	2016 – 2019: 京都大学, 数理解析研究所, 教授 2011 – 2016: 京都大学, 数理解析研究所, 准教授 2013: 京都大学, 数理解析研究所, 准教授(Associate Professor) 2011: 東京大学, 情報理工学(系)研究科, 准教授 2007 – 2010: The University of Tokyo, Graduate School of Information and Technology, Associate Professor … More
Review Section/Research Field	Principal Investigator Fundamental theory of informatics / Science and Engineering / Engineering fundamentals / 計算機科学 / Theory of informatics / Medium-sized Section 60:Information science, computer engineering, and related fields Except Principal Investigator Social systems engineering/Safety system / Fundamental theory of informatics / Mathematical informatics / System engineering / 社会システム工学 / Science and Engineering
Keywords	Principal Investigator アルゴリズム / 列挙 / 計算量 / 施設配置問題 / マトロイド / データマイニング / 知識表現 / 推論 / ホーンブール関数 / 部分定義論理関数 … More Except Principal Investigator 組合せ最適化 / 離散最適化 / アルゴリズム / 劣モジュラ関数 / 数理計画 / Algorithms / Discrete Optimization / Combinatorial Optimization / Submodular Functions / アルゴリズム理論 / 計算限界解明 / OR / 細合せ最滴化 / マルコフ連鎖 / 脱乱択化 / 劣モジュラ構造 / 問題解決エンジン / メタヒューリスティクス / CSP(制約充足問題) / 組合せアルゴリズム / タブ-探索 / 制約充足問題 / 一般化割当問題 / 問題解決 / 組合セアルゴリズム / メタ・ヒューリスティックス / problem solving engine / metaheuristics / CSP (constraint satisfaction problem) / combinatorial optimization / ハイパーグラフ / 計算効率 / ネットワーク最適化 / コテリ理論 / Hypergraphs / 大規模システム / Large-Seal Systems / Mathematical Programming / 研究連携促進 / 研究拠点形成 / 若手研究者の育成 / 成果の総括 / 成果の波及 / 計算複雑さの理論 / 計算量上下界解析 / 成果の総括と公表 / 計算限界解明手法の開拓 / 多視点からの連携研究 / 国際研究者交流 / 各種啓発・研究成果波及 / 若手研究者育成 / 多視点からの統合的解析 / 計算限界研究センター / 計算理論若手研究者育成 / ELC 秋学校 / ELC Seminar / ELC Workshop / 研究成果とりまとめ / 計算限界 / 成果のとりまとめ / 若手育成 / 啓発活動 Less

局所構造を利用した高速なアルゴリズムの開発Principal InvestigatorOngoing
- Principal Investigator
  
  牧野和久
- Project Period (FY)
  2019 – 2021
- Research Category
  
  Challenging Research (Exploratory)
- Review Section
  
  Medium-sized Section 60:Information science, computer engineering, and related fields
- Research Institution
  Kyoto University
Exploring the Limits of Computation
- Principal Investigator
  
  渡辺治
- Project Period (FY)
  2017
- Research Category
  
  Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
- Research Institution
  Tokyo Institute of Technology
Development of efficient algorithms based on enumeration structuresPrincipal InvestigatorOngoing
- Principal Investigator
  
  牧野和久
- Project Period (FY)
  2014 – 2018
- Research Category
  
  Grant-in-Aid for Scientific Research (B)
- Research Field
  
  Theory of informatics
- Research Institution
  Kyoto University
劣モジュラ的な離散構造に注目した最適化基礎理論の展開と高速アルゴリズム開発Ongoing
- Principal Investigator
  
  藤重悟
- Project Period (FY)
  2013 – 2018
- Research Category
  
  Grant-in-Aid for Scientific Research (B)
- Research Field
  
  Mathematical informatics
- Research Institution
  Kyoto University
Deterministic Random Walk
- Principal Investigator
  
  KIJIMA Shuji
- Project Period (FY)
  2012
- Research Category
  
  Grant-in-Aid for Challenging Exploratory Research
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  Kyushu University
Exploring the limits of computation from mathematical logicPrincipal Investigator
- Principal Investigator
  
  Makino Kazuhisa
- Project Period (FY)
  2012 – 2016
- Research Category
  
  Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
- Review Section
  
  Science and Engineering
- Research Institution
  Kyoto University
A Multifaced Approach Toward Understanding the Limitations of Compuation
- Principal Investigator
  
  Watanabe Osamu
- Project Period (FY)
  2012 – 2016
- Research Category
  
  Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)
- Review Section
  
  Science and Engineering
- Research Institution
  Tokyo Institute of Technology
Basic studies on discrete enumeration algorithmsPrincipal Investigator
- Principal Investigator
  
  MAKINO Kazuhisa
- Project Period (FY)
  2010 – 2014
- Research Category
  
  Grant-in-Aid for Scientific Research (C)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  Kyoto University
  The University of Tokyo
Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures
- Principal Investigator
  
  FUJISHIGE Satoru
- Project Period (FY)
  2008 – 2012
- Research Category
  
  Grant-in-Aid for Scientific Research (B)
- Research Field
  
  Social systems engineering/Safety system
- Research Institution
  Kyoto University
Studies on algorithms for large-scale discrete generation problemsPrincipal Investigator
- Principal Investigator
  
  MAKINO Kazuhisa
- Project Period (FY)
  2006 – 2008
- Research Category
  
  Grant-in-Aid for Young Scientists (A)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  The University of Tokyo
ブール理論に基づく離散システムの構造解析と計算限界の研究Principal Investigator
- Principal Investigator
  
  牧野和久
- Project Period (FY)
  2004 – 2007
- Research Category
  
  Grant-in-Aid for Scientific Research on Priority Areas
- Review Section
  
  Science and Engineering
- Research Institution
  The University of Tokyo
  Osaka University
Analysis of Large-scale Discrete Optimization Problems and Development of Efficient Algorithms Based on Submodularity Structures
- Principal Investigator
  
  FUJISHIGE Satoru
- Project Period (FY)
  2004 – 2007
- Research Category
  
  Grant-in-Aid for Scientific Research (B)
- Research Field
  
  Social systems engineering/Safety system
- Research Institution
  Kyoto University
離散構造を有する列挙問題の解法に関する研究Principal Investigator
- Principal Investigator
  
  牧野和久
- Project Period (FY)
  2003 – 2005
- Research Category
  
  Grant-in-Aid for Young Scientists (B)
- Research Field
  
  Fundamental theory of informatics
- Research Institution
  The University of Tokyo
  Osaka University
ネットワークフロー問題に対する高速かつ実用的アルゴリズムに関する研究Principal Investigator
- Principal Investigator
  
  牧野和久
- Project Period (FY)
  2001 – 2002
- Research Category
  
  Grant-in-Aid for Young Scientists (B)
- Research Field
  
  計算機科学
- Research Institution
  Osaka University
Fundamental Research on Fast Algorithms for Large-Scale Discrete Optimization Problems Based on Submodularity Structures
- Principal Investigator
  
  FUJISHIGE Satoru
- Project Period (FY)
  2001 – 2003
- Research Category
  
  Grant-in-Aid for Scientific Research (B)
- Research Field
  
  社会システム工学
- Research Institution
  KYOTO UNIVERSITY
  Osaka University
現実データからの知識獲得問題に対するブール関数的アプローチPrincipal Investigator
- Principal Investigator
  
  牧野和久
- Project Period (FY)
  1999 – 2000
- Research Category
  
  Grant-in-Aid for Encouragement of Young Scientists (A)
- Research Field
  
  Engineering fundamentals
- Research Institution
  Osaka University
Computational Efficiency of Discrete Optimization Algorithms and Discrete Structures
- Principal Investigator
  
  FUJISHIGE Satoru
- Project Period (FY)
  1998 – 2000
- Research Category
  
  Grant-in-Aid for Scientific Research on Priority Areas (B)
- Research Institution
  Osaka University
Studies on combinatorial algorithms as problem solving engine
- Principal Investigator
  
  IBARAKI Toshihide
- Project Period (FY)
  1996 – 1998
- Research Category
  
  Grant-in-Aid for Scientific Research (A)
- Research Field
  
  System engineering
- Research Institution
  KYOTO UNIVERSITY

[Book] Algorithms and Computation, 26th International Symposium ISAAC 20152015
- Author(s)
  K. Elbassioni and K. Makino (Eds)
- Total Pages
  793
- Publisher
  Springer-Verlag
- Data Source
  KAKENHI-ORGANIZER-24106001
[Journal Article] Optimal Matroid Partitioning Problems2017
- Author(s)
  Yasushi Kawas, Kei Kimura, Kazuhisa Makino, Hanna Sumita
- Journal Title
  
  LIPIcs
  
  Volume: 92
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-26280001
[Journal Article] Online Knapsack Problem Under Concave Functions2017
- Author(s)
  Han Xin、Ma Ning、Makino Kazuhisa、Chen He
- Journal Title
  
  LNCS
  
  Volume: 10336 Pages: 103-114
- DOI
  10.1007/978-3-319-59605-1_10
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-26280001
[Journal Article] A nested family of $$\varvec{k}$$ k -total effective rewards for positional games2017
- Author(s)
  Boros Endre、Elbassioni Khaled、Gurvich Vladimir、Makino Kazuhisa
- Journal Title
  
  International Journal of Game Theory
  
  Volume: 46 Pages: 263-293
- DOI
  10.1007/s00182-016-0532-z
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-26280001
[Journal Article] A representation of antimatroids by Horn rules and its application to educational systems2017
- Author(s)
  H. Yoshikawa, H. Hirai, and K. Makino
- Journal Title
  
  Journal of Mathematical Psychology
  
  Volume: 77 Pages: 82-93
- DOI
  10.1016/j.jmp.2016.09.002
- Peer Reviewed / Acknowledgement Compliant
- Data Source
  KAKENHI-PROJECT-25280004
[Journal Article] Posimodular Function Optimization2017
- Author(s)
  Magnus M. Halldorsson, Toshimasa Ishii，Kazuhisa Makino, Kenjiro Takazawa
- Journal Title
  
  Proc. Algorithms and Data Structure Symposium
  
  Volume: 10389 Pages: 437-448
- DOI
  10.1007/978-3-319-62127-2_37
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-16K00001, KAKENHI-PROJECT-16K16012, KAKENHI-PROJECT-26280001, KAKENHI-WRAPUP-17H06074, KAKENHI-PROJECT-15H02965
[Journal Article] Parameterized Complexity of Sparse Linear Complementarity Problems2017
- Author(s)
  Hanna Sumita, Naonori Kakimura, and Kazuhisa Makino
- Journal Title
  
  Algorithmica
  
  Volume: 掲載確定 Pages: 42-65
- DOI
  10.1007/s00453-016-0229-5
- Peer Reviewed / Acknowledgement Compliant
- Data Source
  KAKENHI-PROJECT-25730001, KAKENHI-PROJECT-26280001, KAKENHI-WRAPUP-17H06074
[Journal Article] A convex programming-based algorithm for mean payoff stochastic games with perfect information2017
- Author(s)
  Boros Endre、Elbassioni Khaled、Gurvich Vladimir、Makino Kazuhisa
- Journal Title
  
  Optimization Letters
  
  Volume: 11 Pages: 1499-1512
- DOI
  10.1007/s11590-017-1140-y
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-25280004
[Journal Article] Strong Duality in Horn Minimization2017
- Author(s)
  Boros Endre、Cepek Ondrej、Makino Kazuhisa
- Journal Title
  
  LNCS
  
  Volume: 10472 Pages: 123-135
- DOI
  10.1007/978-3-662-55751-8_11
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-26280001
[Journal Article] Surrogate Optimization for p-Norms2016
- Author(s)
  Yasushi Kawase, Kazuhisa Makino
- Journal Title
  
  Leibniz International Proceedings in Informatics (LIPIcs)
  
  Volume: 64
- DOI
  10.4230/LIPIcs.ISAAC.2016.41
- Language
  English
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-26280001
[Journal Article] Online minimization knapsack problem2016
- Author(s)
  X. Han and K. Makino
- Journal Title
  
  Theor. Comput. Sci.
  
  Volume: 609 Pages: 185-196
- DOI
  10.1016/j.tcs.2015.09.021
- Peer Reviewed / Acknowledgement Compliant / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-25280004, KAKENHI-PLANNED-24106002
[Journal Article] Sufficient conditions for the existence of Nash equilibria in bimatrix games in terms of forbidden $$2 \times 2$$ 2 × 2 subgames2016
- Author(s)
  Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino, Vladimir Oudalov
- Journal Title
  
  International Journal of Game Theory
  
  Volume: 45 Pages: 1111-1131
- DOI
  10.1007/s00182-015-0513-7
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] Optimal Composition Ordering Problems for Piecewise Linear Functions2016
- Author(s)
  Yasushi Kawase, Kazuhisa Makino, Kento Seimi
- Journal Title
  
  Leibniz International Proceedings in Informatics (LIPIcs)
  
  Volume: 64
- DOI
  10.4230/LIPIcs.ISAAC.2016.42
- Language
  English
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-26280001
[Journal Article] Trichotomy for integer linear systems based on their sign patterns2016
- Author(s)
  Kei Kimura and Kazuhisa Makino
- Journal Title
  
  Discrete Applied Mathematics
  
  Volume: VOL.200 Pages: 67-78
- DOI
  10.1016/j.dam.2015.07.004
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-15H06286, KAKENHI-PLANNED-24106002
[Journal Article] A Multiplicative Weights Update Algorithm for Packing and Covering Semi-infinite Linear Programs2016
- Author(s)
  Khaled Elbassioni, Kazuhisa Makino, Waleed Najy
- Journal Title
  
  Lecture Notes in Computer Science
  
  Volume: 10138 Pages: 78-91
- DOI
  10.1007/978-3-319-51741-4_7
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-26280001
[Journal Article] Parameterized algorithms for parity games2015
- Author(s)
  Jakub Gajarsk´y, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak
- Journal Title
  
  Lecture Notes in Computer Science
  
  Volume: 9235 Pages: 336-347
- DOI
  10.1007/978-3-662-48054-0
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Randomized algorithms for online knapsack problems2015
- Author(s)
  Xin Han, Yasushi Kawase, Kazuhisa Makino
- Journal Title
  
  Theor. Comput. Sci.
  
  Volume: 562 Pages: 395-405
- DOI
  10.1016/j.tcs.2014.10.017
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PLANNED-24106002, KAKENHI-PROJECT-26280001
[Journal Article] Parameterized Complexity of Sparse Linear Complementarity Problems2015
- Author(s)
  H. Sumita, N. Kakimura, and K. Makino
- Journal Title
  
  LIPIcs
  
  Volume: 43 Pages: 355-364
- DOI
  10.4230/LIPIcs.IPEC.2015.355
- Language
  English
- Peer Reviewed / Open Access / Acknowledgement Compliant / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-25280004, KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] Deterministic random walks on finite graphs2015
- Author(s)
  Shuji Kijima, Kentaro Koga, Kazuhisa Makino
- Journal Title
  
  Random Structures and Algorithms
  
  Volume: 46 Pages: 739-761
- DOI
  10.1002/rsa.20533
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-26280001, KAKENHI-PROJECT-25700002, KAKENHI-PLANNED-24106002
[Journal Article] Proportional cost buyback problem with weight bounds2015
- Author(s)
  Yasushi Kawase, Xin Han, Kazuhisa Makino
- Journal Title
  
  Lecture Notes in Computer Science
  
  Volume: LNCS9486 Pages: 794-808
- DOI
  10.1007/978-3-319-26626-8_59
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] The linear complementarity problems with a few variables per constraint2015
- Author(s)
  Hanna Sumita, Naonori Kakimura and Kazuhisa Makino
- Journal Title
  
  Math. Oper. Res.
  
  Volume: 40 Pages: 1015-1026
- DOI
  10.1287/moor.2014.0708
- Peer Reviewed / Acknowledgement Compliant
- Data Source
  KAKENHI-PROJECT-25730001, KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] Parameterized Algorithms for Parity Games2015
- Author(s)
  Jakub Gajarský, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak
- Journal Title
  
  MFCS
  
  Volume: LNCS9235 Pages: 336-347
- DOI
  10.1007/978-3-662-48054-0_28
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-26280001
[Journal Article] On randomized fictitious play for approximating saddle points over convex sets2015
- Author(s)
  Khaled M. Elbassioni, Kazuhisa Makino, Kurt Mehlhorn, Fahimeh Ramezani
- Journal Title
  
  Algorithmica
  
  Volume: 73 Pages: 441-459
- DOI
  10.1007/s00453-014-9902-8
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] Markov Decision Processes and Stochastic Games with Total Effective Payoff2015
- Author(s)
  Endre Boros ,Khaled Elbassioni,Vladimir Gurvich, Kazuhisa Makino
- Journal Title
  
  STACS 2015
  
  Volume: 30 Pages: 103-115
- DOI
  10.4230/LIPIcs.STACS.2015.103
- Language
  English
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] Online Unweighted Knapsack Problem with Removal Cost2014
- Author(s)
  Xin Han,Yasushi Kawase, Kazuhisa Makino
- Journal Title
  
  Algorithmica
  
  Volume: 70 Pages: 76-91
- DOI
  10.1007/s00453-013-9822-z
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games2014
- Author(s)
  Endre Boros ,Khaled Elbassioni,Vladimir Gurvich, Kazuhisa Makino
- Journal Title
  
  COCOA 2014
  
  Volume: 8881 Pages: 694-709
- DOI
  10.1007/978-3-319-12691-3_52
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] Parameterized Edge Hamiltonicity2014
- Author(s)
  Michael Lampis, Kazuhisa Makino, Valia Mitsou, Yushi Uno
- Journal Title
  
  WG 2014
  
  Volume: LNCS8747 Pages: 348-359
- DOI
  10.1007/978-3-319-12340-0_29
- Peer Reviewed / Int'l Joint Research
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Augmenting Edge-Connectivity between Vertex Subsets2014
- Author(s)
  T. Ishii，K. Makino
- Journal Title
  
  Algorithmica
  
  Volume: - Pages: 130-147
- DOI
  10.1007/s00453-012-9724-5
- Peer Reviewed / Acknowledgement Compliant
- Data Source
  KAKENHI-PROJECT-23310098, KAKENHI-PROJECT-24700001, KAKENHI-PLANNED-24106002
[Journal Article] Online Removable Knapsack Problem under Convex Function2014
- Author(s)
  Xin Han,Yasushi Kawase, Kazuhisa Makino, He Guo
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 540 Pages: 62-69
- DOI
  10.1016/j.tcs.2013.09.013
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
[Journal Article] On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness2013
- Author(s)
  Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino
- Journal Title
  
  Operations Research Letter
  
  Volume: 41
- DOI
  10.1016/j.orl.2013.04.006
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Randomized Algorithms for Removable Online Knapsack Problems2013
- Author(s)
  Xin Han, Yasushi Kawase, Kazuhisa Makino
- Journal Title
  
  LNCS
  
  Volume: 7924 Pages: 60-71
- DOI
  10.1007/978-3-642-38756-2_9
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500007, KAKENHI-PLANNED-24106002
[Journal Article] A Complexity Index for Integer Linear Systems Based on Their Sign Patterns2013
- Author(s)
  Kei Kimura, Kazuhisa Makino
- Journal Title
  
  Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
  
  Volume: 8 Pages: 333-337
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Unit Cost Buyback Problem2013
- Author(s)
  Xin Han, Yasushi Kawase, Kazuhisa Makino
- Journal Title
  
  LNCS
  
  Volume: 8283 Pages: 435-445
- DOI
  10.1007/978-3-642-45030-3_41
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500007, KAKENHI-PLANNED-24106002
[Journal Article] On Canonical Forms for Zero-Sum Stochastic Mean Payoff Games2013
- Author(s)
  Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino
- Journal Title
  
  Dynamic Games and Applications
  
  Volume: 3 Pages: 128-161
- DOI
  10.1007/s13235-013-0075-x
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Sparse Linear Complementarity Problems2013
- Author(s)
  Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
- Journal Title
  
  LNCS
  
  Volume: 7878 Pages: 358-369
- DOI
  10.1007/978-3-642-38233-8
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Robust Matchings and Matroid Intersections2013
- Author(s)
  R. Fujita, Y. Kobayashi, and K. Makino
- Journal Title
  
  SIAM J. Discrete Math.
  
  Volume: 27 Pages: 1234-1256
- DOI
  10.1137/100808800
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-21360045, KAKENHI-PROJECT-22500007, KAKENHI-PLANNED-24106002, KAKENHI-PROJECT-24700004
[Journal Article] Sparse Linear Complementarity Problems2013
- Author(s)
  Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
- Journal Title
  
  Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
  
  Volume: 8 Pages: 453-462
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Nash equilibria with minimum potential in undirected broadcast games2013
- Author(s)
  Yasushi Kawase, Kazuhisa Makino
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 482 Pages: 33-47
- DOI
  10.1016/j.tcs.2013.02.031
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002, KAKENHI-PROJECT-25280004
[Journal Article] Robust Independence Systems2013
- Author(s)
  Naonori Kakimura, Kazuhisa Makino
- Journal Title
  
  SIAM Journal on Discrete Mathematics
  
  Volume: 27 Pages: 1257-1273
- DOI
  10.1137/120899480
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500007, KAKENHI-PLANNED-24106002, KAKENHI-PROJECT-25730001
[Journal Article] A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions2013
- Author(s)
  Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino
- Journal Title
  
  LNCS
  
  Volume: 7965 Pages: 220-231
- DOI
  10.1007/978-3-642-39206-1_19
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets2013
- Author(s)
  Khaled Elbassioni, Kazuhisa Makino, Kurt Mehlhorn, Fahimeh Ramezani
- Journal Title
  
  LNCS
  
  Volume: 7936 Pages: 65-76
- DOI
  10.1007/978-3-642-38768-5_8
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Derandomizing HSSW algorithm for 3-SAT2013
- Author(s)
  Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
- Journal Title
  
  Algorithmica
  
  Volume: 未定 Pages: 112-124
- DOI
  10.1007/s00453-012-9741-4
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22240001, KAKENHI-PROJECT-22500007, KAKENHI-PLANNED-24106002, KAKENHI-PLANNED-24106003, KAKENHI-PROJECT-25240002
[Journal Article] Online Unweighted Knapsack Problem with Removal Cost2013
- Author(s)
  Xin Han, Yasushi Kawase, Kazuhisa Makino
- Journal Title
  
  Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
  
  Volume: 8 Pages: 191-200
- Peer Reviewed
- Data Source
  KAKENHI-PLANNED-24106002
[Journal Article] Computing Knapsack Solutions with Cardinality Robustness2012
- Author(s)
  N. Kakimura, K. Makino, and K. Seimi
- Journal Title
  
  Japan Journal of Industrial and Applied Mathematics
  
  Volume: Vol.29 Pages: 469-483
- DOI
  10.1007/s13160-012-0075-z
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088, KAKENHI-PROJECT-21760057, KAKENHI-PLANNED-24106002
[Journal Article] Deductive Inference for the Interiors and Exteriors of Horn Theories2012
- Author(s)
  Kazuhisa Makino, Hirotaka Ono
- Journal Title
  
  ACM Transactions on Computational Logic
  
  Volume: 13(3) Pages: 23-23
- DOI
  10.1145/2287718.2287723
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-21680001, KAKENHI-PLANNED-24106002
[Journal Article] Source Location Problems with Flow Requirements2012
- Author(s)
  K. Makino
- Journal Title
  
  Proceedings of the Third International Conference on Networking and Computing
  
  Volume: 13 Pages: 404-406
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500007
[Journal Article] An exact algorithm for the Boolean connectivity problem for k-CNF2011
- Author(s)
  Kazuhisa Makino
- Journal Title
  
  Theoretical Computer Scicne
  
  Volume: 412 Pages: 4613-4618
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500007
[Journal Article] On the Boolean connectivity problem for Horn relations.2010
- Author(s)
  K.Makino, S.Tamaki, M.Yamamoto
- Journal Title
  
  Discrete Applied Mathematics 158(18)
  
  Pages: 2024-2030
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Online removable knapsack with limited cuts2010
- Author(s)
  Xin Han, Kazuhisa Makino
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 411 Pages: 3956-3964
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500007
[Journal Article] On the Boolean connectivity problem for Horn relations2010
- Author(s)
  K.Makino, S.Tamaki, M.Yamamoto
- Journal Title
  
  Discrete Applied Mathematics
  
  Volume: 158 Pages: 2024-2030
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Left-to-Right Multiplication for Monotone Boolean Dualization2010
- Author(s)
  Endre Boros, Khaled Elbassioni, Kazuhisa Makino
- Journal Title
  
  SIAM Journal on Computing
  
  Volume: 39 Pages: 3424-3439
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500007
[Journal Article] Acyclic, or totally tight, two-person game forms : Characterization and main properties2010
- Author(s)
  Endre Boros, Vladimir Gurvich, Kazuhisa Makino, David Papp
- Journal Title
  
  Discrete Mathematics
  
  Volume: 310 Pages: 1135-1151
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-22500007
[Journal Article] On the Boolean connectivity problem for Horn relations2010
- Author(s)
  K. Makino, S.Tamaki, and M. Yamamoto
- Journal Title
  
  Discrete Applied Mathematics
  
  Volume: Vol.158 Pages: 2024-2030
- DOI
  10.1016/j.dam.2010.08.019
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Minimum transversals in posi-modular systems2009
- Author(s)
  M.Sakashita, K.Makino, H.Nagamochi, S.Fujishige
- Journal Title
  
  SIAM Journal on Discrete Mathematics 23
  
  Pages: 858-871
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] A Fast and Simple Parallel Algorithm for the Monotone Duality Problem, ICALP 20092009
- Author(s)
  E. Boros, K. Makino
- Journal Title
  
  Lecture Notes in Computer Science Vol.5555
  
  Pages: 183-194
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] A Fast and Simple Parallel Algorithm for the Monotone Duality Problem2009
- Author(s)
  E.Boros, K.Makino
- Journal Title
  
  ICALP 2009, Lecture Notes in computer Science 5555
  
  Pages: 183-194
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Minimum transversals in posi-modular systems.2009
- Author(s)
  M.Sakashita, K.Makino, H.Nagamochi, S.Fujishige
- Journal Title
  
  SIAM Journal on Discrete Mathematics 23
  
  Pages: 858-871
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs2009
- Author(s)
  Khaled Elbassioni, Kazuhisa Makino, Imran Rauf
- Journal Title
  
  ESA 2009, Lecture Notes in computer Science 5757
  
  Pages: 143-154
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] On the readability of monotone Boolean formulae2009
- Author(s)
  K.M.Elbassioni, K.Makino, I.Rauf
- Journal Title
  
  Proceedings of COCOON 2009
  
  Pages: 496-505
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Minimum transversals in posi-modular systems2009
- Author(s)
  M. Sakashita, K. Makino, H. Nagamochi,and S. Fujishige
- Journal Title
  
  SIAM Journal on Discrete Mathematics
  
  Volume: Vol.23 Pages: 858-871
- DOI
  10.1137/060663970
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs2009
- Author(s)
  K. Elbassioni, K. Makino, I. Rauf
- Journal Title
  
  ESA 2009, Lecture Notes in Computer Science Vol.5757
  
  Pages: 143-154
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Minimizing a monotone concave function with laminar covering constraints.2008
- Author(s)
  Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige
- Journal Title
  
  Discrete Applied Mathematics 156
  
  Pages: 2035-2049
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] Minimizing a monotone concave function with laminar covering constraints2008
- Author(s)
  M. Sakashita, K. Makino, S. Fujishige
- Journal Title
  
  Discrete Applied Mathematics 156
  
  Pages: 2004-2019
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Minimum cost source location problems with flow requirements.2008
- Author(s)
  M. Sakashita, K. Makino and S. Fujishige
- Journal Title
  
  Algorithmica 50
  
  Pages: 555-583
- Description
  「研究成果報告書概要(和文)」より
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Minimizing a monotone concave function with laminar covering constraints2008
- Author(s)
  M.Sakashita, K.Makino, and S.Fujishige
- Journal Title
  
  Discrete Applied Mathematics
  
  Volume: Vol.156 Pages: 2004-2019
- DOI
  10.1016/j.dam.2007.04.016
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Minimum Cost Source Location Problems with Flow Requirements2008
- Author(s)
  Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige
- Journal Title
  
  Algorithmica 50
  
  Pages: 555-583
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] Minimum Cost Source Location Problems with Flow Requirements2008
- Author(s)
  M. Sakashita, K. Makino, and S.Fujishige
- Journal Title
  
  Algorithmica
  
  Volume: Vol.50 Pages: 555-583
- DOI
  10.1007/s00453-007-9012-y
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Minimum cost source location problems with flow requirements2008
- Author(s)
  M., Sakashita, K., Makino, S., Fujishige
- Journal Title
  
  Algorithmica 50
  
  Pages: 555-583
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Minimum Cost Source Location Problems with Flow Requirements2008
- Author(s)
  M. Sakashita, K. Makino, S. Fujishige
- Journal Title
  
  Algorithmica 50
  
  Pages: 555-583
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-20310088
[Journal Article] Deductive Inference for the Interiors and Exteriors of Horn Theories2008
- Author(s)
  Kazuhisa Makino, Hirotaka Ono
- Journal Title
  
  ISAAC 2008, Lecture Notes in Computer Science 5369
  
  Pages: 390-401
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] Generating Minimal k-Vertex Connected Spanning Subgraphs2007
- Author(s)
  L. Khachiyan, K. Borys, E. Boros, K. Elbassinoi, V. Gurvich, K. Makino, G. Rudolf
- Journal Title
  
  COCOON 2007, LNCS 4598
  
  Pages: 222-231
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data2007
- Author(s)
  L. Khachiyan, E. Boros, K. Elbassinoi, V. Gurvich, K. Makino
- Journal Title
  
  Theoretical Computer Science Vol.379
  
  Pages: 361-376
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Enumerating disjunctions and conjunctions of paths and cuts in reliability theory2007
- Author(s)
  L., Khachiyan, E., Boros, K., Elbassioni, V., Gurvich, K., Makino
- Journal Title
  
  Discrete Applied Mathematics 155
  
  Pages: 137-149
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] On the Fractional Chromatic Number of Monotone Self-dual Boolean Functions2007
- Author(s)
  Daya Ram Gaur, Kazuhisa Makino
- Journal Title
  
  FAW 2007, Lecture Notes in Computer Science 4613
  
  Pages: 148-159
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] Generating Minimal k-Vertex Connected Spanning Subgraphs2007
- Author(s)
  L. Khachiyan, K. Borys, E. Boros, K. Elbassinoi, V. Gurvich, K. Makino, G. Rudolf
- Journal Title
  
  COCOON 2007, LNCS Vol.4598
  
  Pages: 222-231
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Enumerating Spanning and Connected Subsets in Graphs and Matroids2007
- Author(s)
  L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, K. Makino
- Journal Title
  
  ESA 2006, Lecture Notes in Computer Science Vol.155
  
  Pages: 444-455
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Enumerating disjunctions and conjunctions of paths and cuts in reliability theory2007
- Author(s)
  L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, K. Makino
- Journal Title
  
  Discrete Applied Mathematics Vol.155
  
  Pages: 137-149
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Minimizing a monotone concave.function with laminar covering constraints2007
- Author(s)
  M., Sakashita, K., Makino, S., Fujishige
- Journal Title
  
  Discrete Applied Mathematics
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Enumerating Spanning and Connected Subsets in Graphs and Matroids2007
- Author(s)
  L.Khachiyan, E.Boros, K.Borys, K.Elbassioni, V.Gurvich, K.Makino
- Journal Title
  
  ESA 2006, Lecture Notes in Computer Science 155
  
  Pages: 444-455
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data.2007
- Author(s)
  L. Khachiyan, E. Boros, K. Elbassinoi, V. Gurvich, K. Makino
- Journal Title
  
  Theoretical Computer Science 379
  
  Pages: 361-376
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Enumerating disjunctions and conjunctions of paths and cuts in reliability theory.2007
- Author(s)
  L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich and K. Makino
- Journal Title
  
  Discrete Applied Mathematics 155
  
  Pages: 137-149
- Description
  「研究成果報告書概要(和文)」より
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Finding Intersections of Bichromatic Segments Defined by Points2007
- Author(s)
  A. Elmasry, K. Makino
- Journal Title
  
  CCCG 2007 19
  
  Pages: 269-272
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Finding Intersections of Bichromatic Segments Defined by Points2007
- Author(s)
  A. Elmasry, K. Makino
- Journal Title
  
  CCCG 2007 Vol.19
  
  Pages: 269-272
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Enumerating disjunctions and conjunctions of paths and cuts in reliability theory2007
- Author(s)
  L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, and K. Makino
- Journal Title
  
  Discrete Applied Mathematics 155
  
  Pages: 137-149
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Enumerating disjunctions and conjunctions of paths and cuts in reliability theory2007
- Author(s)
  L.Khachiyan, E.Boros, K.Elbassioni, V.Gurvich, K.Makino
- Journal Title
  
  Discrete Applied Mathematics 155
  
  Pages: 137-149
- Data Source
  KAKENHI-PROJECT-18680002
[Journal Article] Minimizing a monotone concave function with laminar covering constraints.2007
- Author(s)
  M. Sakashita, K. Makino and S. Fujishige
- Journal Title
  
  Discrete Applied Mathematics, availableonline on May 10, 2007
- Description
  「研究成果報告書概要(和文)」より
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] On the Boolean Connectivity Problem for Horn Relations2007
- Author(s)
  Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto
- Journal Title
  
  SAT 2007, Lecture Notes in Computer Science 4501
  
  Pages: 187-200
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] An O(n log^2 n) algorithm for the optimal sink location problem on dynamic tree networks2006
- Author(s)
  S.Mamada, T.Uno, K.Makino, S.Fujishige
- Journal Title
  
  Discrete Applied Mathematics 154
  
  Pages: 2387-2401
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Minimum Ciost Location Problems with Flow Requirements2006
- Author(s)
  M.Sakashita, K.Makino, S.Fujishige
- Journal Title
  
  Lecture Notes in Computer Science 3887
  
  Pages: 769-780
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] How to Collect Balls Moving in the Euclidean Plane2006
- Author(s)
  Y.Asahiro, T.Horiyama, K.Makino, H.Ono, T.Sakuma
- Journal Title
  
  Discrete Applied Mathematics 154
  
  Pages: 2247-2262
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] Minimum Edge Ranking Spanning Trees of Split Graphs2006
- Author(s)
  K.Makino, U.Uno, T.Ibaraki
- Journal Title
  
  Discrete Applied Mathematics 154
  
  Pages: 2373-2386
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] An O (n log^2 n) algorithm for the optimal sink location problem in dynamic tree networks2006
- Author(s)
  S.Mamada, T.Uno, K.Makino, S.Fujishige
- Journal Title
  
  Discrete Applied Mathematics 154
  
  Pages: 2387-2401
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] A polynomial time algorithm for evacuation problem in tree dynamic networks with multiple exits.2006
- Author(s)
  S.Mamada, T.Uno, K.Makino, S.Fujishige
- Journal Title
  
  Complex Systems Approaches for Safety, Security and Reliability (SSR 2006) (掲載予定)
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] An O(n log^2 n) algorithm for the optimal sink location problem on dynamic tree networks2006
- Author(s)
  S., Mamada, T., Uno, K., Makino, S., Fujishige
- Journal Title
  
  Discrete Applied Mathematics 154
  
  Pages: 2387-2401
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] On the Complexity of Some Enumeration Problems for Matroids2006
- Author(s)
  L.Khachiyan, E.Boros, K.Elbassioni, V.Gurvich, K.Makino
- Journal Title
  
  SIAM Journal on Discrete Mathematics 19
  
  Pages: 966-984
- Data Source
  KAKENHI-PROJECT-15700013
[Journal Article] Minimum Cost source location problems with flow requirements.2006
- Author(s)
  M.Sakashita, K.Makino, S.Fujishige
- Journal Title
  
  Lecture Notes in Computer Science (LATIN 2006) 3887
  
  Pages: 769-780
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Minimum Transversals in Posi-modular Systems2006
- Author(s)
  M.Sakashita, K.Makino, H.Nagamochi, S.Fujishige
- Journal Title
  
  ESA 2006, Lecture Notes in Computer Science 4168
  
  Pages: 576-587
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] Minimum cost source location problems with flow requirements2006
- Author(s)
  M.Sakashita, K.Makino, S.Fujishige
- Journal Title
  
  Lecture Notes in Computer Science 3887
  
  Pages: 769-780
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] An O(n log^2 n)algorithm for the optimal sink location problem on dynamic tree networks.2006
- Author(s)
  S. Mamada, T. Uno, K. Makino and S. Fujishige
- Journal Title
  
  Discrete Applied Mathematics 154
  
  Pages: 2387-2401
- Description
  「研究成果報告書概要(和文)」より
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Minimum transversals in posi-modular systems2006
- Author(s)
  M.Sakashita, K.Makino, H.Nagamochi, S.Fujishige
- Journal Title
  
  Lecture Notes in Computer Science 4168
  
  Pages: 576-587
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] An O(n log^2 n) Algorithm for the Optimal Sink Location Problem in Dynamic Tree Networks2005
- Author(s)
  S.Mamada, T.Uno, K.Makino, S.Fujishige
- Journal Title
  
  Discrete Applied Mathematics (掲載予定)
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] A tree partitioning problem arising from an evacuation problem in tree dynamic networks with multiple exits2005
- Author(s)
  S.Mamada, T.Uno, K.Makino, S.Fujishige
- Journal Title
  
  Journal of the Operations Research Society of Japan 48
  
  Pages: 196-206
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs2005
- Author(s)
  L.Khachiyan, E.Boros, K.Borys, K.Elbassioni, V.Gurvich, K.Makino
- Journal Title
  
  Lecture Notes in Computer Science 3827
  
  Pages: 156-165
- Data Source
  KAKENHI-PROJECT-15700013
[Journal Article] A tree partitioning problem arising from an evacuation problem in tree dynamic networks.2005
- Author(s)
  S. Mamada, T. Uno, K. Makino and S. Fujishige
- Journal Title
  
  Journal of the Operations Research Society of Japan 48
  
  Pages: 196-206
- Description
  「研究成果報告書概要(和文)」より
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Minimizing a Montone Concave Function with Laminar Covering Constraints. ISAAC 2005:2005
- Author(s)
  M.Sakashita, K.Makino, S.Fujishige
- Journal Title
  
  Lecture Notes in Computer Science 3827
  
  Pages: 71-81
- Data Source
  KAKENHI-PROJECT-16092217
[Journal Article] A tree partitioning problem arising from an evacuation problem in tree dynamic networks2005
- Author(s)
  S., Mamada, T., Uno, K., Makino, S., Fujishige
- Journal Title
  
  Journal of the Operations Research Society of Japan 48
  
  Pages: 196-206
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Minimizing a monotone concave function with laminar covering constraints2005
- Author(s)
  M.Sakashita, K.Makino, S.Fujishige
- Journal Title
  
  Lecture Notes in Computer Science (ISAAC 2005 Algorithms and Computation)(edited by X.Deng, D.-Z.Du) 3827
  
  Pages: 71-81
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] New algorithms for enumerating all maximal cliques2004
- Author(s)
  K.Makino
- Journal Title
  
  Lecture Notes in Computer Science 3111
  
  Pages: 260-272
- Data Source
  KAKENHI-PROJECT-15700013
[Journal Article] Polybasic polyhedra : Structure of polyhedra with edge vectors Of support size at most 22004
- Author(s)
  S.Fujishige, K.Makino, T.Takabatake, K.Kashiwabara
- Journal Title
  
  Discrete Mathematics 280
  
  Pages: 13-27
- Data Source
  KAKENHI-PROJECT-16310111
[Journal Article] Deterministic random walks on finite graphs
- Author(s)
  Shuji Kijima, Kentaro Koga and Kazuhisa Makino
- Journal Title
  
  in Proceedings of the meeting of Analytic Algorithmics and Combinatorics (ANALCO 2012)
- Data Source
  KAKENHI-PROJECT-23650007
[Journal Article] An O(n log 2n) algorithm for the optimal sink location problem in dynamic tree networks
- Author(s)
  S.Mamada, T.Uno, K.Makino, S.Fujishige
- Journal Title
  
  Discrete Applied Mathematics (掲載予定)
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] 線形相補性問題のパラメータ化計算量2015
- Author(s)
  澄田範奈，垣村尚徳，牧野和久
- Organizer
  電子情報通信学会総合大会
- Place of Presentation
  立命館大学
- Year and Date
  2015-03-11
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] Total dual integrality of the linear complementarity problem2015
- Author(s)
  Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
- Organizer
  The 22nd Interna- tional Symposium on Mathematical Pro- gramming
- Place of Presentation
  Pittsurgh
- Year and Date
  2015-07-12
- Int'l Joint Research
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 線形相補性問題のパラメータ化計算量2015
- Author(s)
  澄田範奈，垣村尚徳，牧野和久
- Organizer
  日本オペレーションズ・リサーチ学会春季研究発表会
- Place of Presentation
  東京理科大学
- Year and Date
  2015-03-26
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] Total dual integrality of the linear complementarity problem2015
- Author(s)
  Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
- Organizer
  The 9th Japanese- Hungarian Symposium on Discrete Mathe- matics and Its Applications
- Place of Presentation
  Fukuoka
- Year and Date
  2015-06-02
- Int'l Joint Research
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 正モジュラ関数の最適化2015
- Author(s)
  石井利昌，牧野和久
- Organizer
  FIT2015
- Place of Presentation
  愛媛大学
- Year and Date
  2015-09-15
- Data Source
  KAKENHI-PROJECT-26280001
[Presentation] 重みに上下限をもつ比例コスト買い戻し問題2014
- Author(s)
  河瀬康志，Han Xin，牧野和久
- Organizer
  日本オペレーションズ・リサーチ学会秋期研究発表会
- Place of Presentation
  北海道科学大学
- Year and Date
  2014-08-29
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 方向つき線形相補性問題の計算複雑度2014
- Author(s)
  澄田範奈，垣村尚徳，牧野和久
- Organizer
  日本オペレーションズ・リサーチ学会秋季研究発表会
- Place of Presentation
  北海道科学大学
- Year and Date
  2014-08-28
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 定数個のランダム点をもつ完全情報である二人ゼロ和確率期待ゲームに対する擬多項式時間アルゴリズム2013
- Author(s)
  Endre Boros，Khaled Elbassioni，Vladimir Gurvich，牧野和久
- Organizer
  電子情報通信学会コンピュテーション研究会
- Place of Presentation
  鳥取環境大学
- Year and Date
  2013-09-03
- Invited
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] Sparse Linear Complementarity Problems2013
- Author(s)
  H. Sumita, N. Kakimura, and K. Makino
- Organizer
  8th International Conference on Algorithms and Complexity
- Place of Presentation
  Barcelona, Spain
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] Deterministic random walks on finite graphs,2012
- Author(s)
  Shuji Kijima, Kentaro Koga and Kazuhisa Makino,
- Organizer
  Analytic Algorithmics and Combinatorics (ANALCO 2012)
- Place of Presentation
  Kyoto
- Data Source
  KAKENHI-PROJECT-23650007
[Presentation] Computing Knapsack solutions with cardinality robustness2012
- Author(s)
  N. Kakimura, K. Makino, and K. Seimi
- Organizer
  21st International Symposium on Mathematical Programming (ISMP)
- Place of Presentation
  TU Berlin (Germany)
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] Computing Knapsack Solutions with Cardinality Robustness2012
- Author(s)
  N. Kakimura, K. Makino, and K. Seimi
- Organizer
  21th International Symposium on Mathematical Programming
- Place of Presentation
  Berlin, Germany
- Invited
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] Derandomizing HSSW Algorithm for 3-SAT2011
- Author(s)
  K. Makino, S. Tamaki, and M. Yamamoto
- Organizer
  17th Annual International Computing and Combinatorics Conference
- Place of Presentation
  Dallas, Texas, USA
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] ンダムウォークの脱乱択化 --- 確率と計算2011
- Author(s)
  来嶋秀治, 古賀健太郎, 牧野和久
- Organizer
  日本オペレーションズリサーチ学会「待ち行列」研究部会第228回研究会
- Place of Presentation
  京都大学
- Year and Date
  2011-10-22
- Data Source
  KAKENHI-PROJECT-23650007
[Presentation] 有限グラフ上のランダムウォークの脱乱択化2011
- Author(s)
  来嶋秀治, 古賀健太郎, 牧野和久
- Organizer
  第135回アルゴリズム研究会
- Place of Presentation
  秋田県立大学
- Year and Date
  2011-05-16
- Data Source
  KAKENHI-PROJECT-23650007
[Presentation] Computing Knapsack Solutions with Cardinality Robustness2011
- Author(s)
  N. Kakimura, K. Makino, and K. Seimi
- Organizer
  22nd International Symposium on Algorithms and Computation
- Place of Presentation
  横浜
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] A pumping algorithm for ergodic stochastic mean payoff games with perfect information.2010
- Author(s)
  E.Boros, K.M.Elbassioni, V.Gurvich, K.Makino
- Organizer
  IPCO 2010.
- Place of Presentation
  Lausanne (Switzerland)
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] A pumping algorithm for ergodic stochastic mean payoff games with perfect information.2010
- Author(s)
  E. Boros, K. M. Elbassioni, V. Gurvich, and K. Makino
- Organizer
  IPCO 2010
- Place of Presentation
  Lausanne (Switzerland)
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] Pumping algorithm for ergodic stochastic mean payoff games with perfect information2010
- Author(s)
  E.Boros, K.M.Elbassioni, V.Gurvich, K.Makino
- Organizer
  The 14^<th> Conference on Integer Programming and Combinatorial Optmization (IPCO)
- Place of Presentation
  Lausanne, Switzerland
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] On the readability of monotone Boolean formulae2009
- Author(s)
  K.M.Elbassioni, K.Makino, I.Rauf
- Organizer
  COCOON 2009. Conference Center Niagara Falls
- Place of Presentation
  (USA)
- Data Source
  KAKENHI-PROJECT-20310088
[Presentation] Minimum transversals in posi-modular systems.2006
- Author(s)
  M. Sakashita, K. Makino, H. Nagamochi and S. Fujishige
- Organizer
  ESA 2006
- Place of Presentation
  Zurich, Switzerland
- Description
  「研究成果報告書概要(和文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] Minimum cost source location problems with flow requirements2006
- Author(s)
  M., Sakashita, K., Makino, S., Fujishige
- Organizer
  LATIN 2006
- Place of Presentation
  Valdivia, Chile
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] Minimum transversals in posi-modular systems2006
- Author(s)
  M., Sakashita, K., Makino, H., Nagamochi, S., Fujishige
- Organizer
  ESA 2006
- Place of Presentation
  Zurich, Switzerland
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] Minimum cost source location problems with flow require ments.2006
- Author(s)
  M. Sakashita, K. Makino and S. Fujishige
- Organizer
  LATIN 2006
- Place of Presentation
  Valdivia, Chile
- Description
  「研究成果報告書概要(和文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] Minimizing a monotone concave function with laminar covering constraints2005
- Author(s)
  M., Sakashita, K., Makino, S., Fujishige
- Organizer
  ISAAC 2005
- Place of Presentation
  Hainan, China
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] Minimizing a monotone concave function with laminar covering constraints.2005
- Author(s)
  M. Sakashita, K. Makino and S. Fujishige
- Organizer
  ISAAC 2005
- Place of Presentation
  Hainan, China
- Description
  「研究成果報告書概要(和文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] An O(n log^2 n)algorithm for the optimal sink location problem in dynamic tree networks.2004
- Author(s)
  S. Mamada, T. Uno, K. Makino and S. Fujishige
- Organizer
  IFIP TCS 2004
- Place of Presentation
  Toulouse, France
- Description
  「研究成果報告書概要(和文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] An O(n log^2 n) algorithm for the optimal sink location problem in dynamic tree networks2004
- Author(s)
  S., Mamada, T. Uno, K., Makino, S., Fujishige
- Organizer
  IFIP TCS 2004
- Place of Presentation
  Toulouse, France
- Description
  「研究成果報告書概要(欧文)」より
- Data Source
  KAKENHI-PROJECT-16310111
[Presentation] 線形相補性問題の整数性
- Author(s)
  澄田範奈，垣村尚徳，牧野和久
- Organizer
  2014年研究集会「最適化：モデリングとアルゴリズム」
- Place of Presentation
  政策研究大学院大学
- Year and Date
  2014-03-25 – 2014-03-26
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 線形相補性問題の完全双対整数性
- Author(s)
  澄田範奈，垣村尚徳，牧野和久
- Organizer
  電子情報通信学会総合大会
- Place of Presentation
  新潟大学
- Year and Date
  2014-03-18 – 2014-03-21
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] Randomized Algorithms for Online Knapsack Problems
- Author(s)
  Han Xin, 河瀬康志, 牧野和久
- Organizer
  情報処理学会アルゴリズム研究会
- Place of Presentation
  岩手県花巻市
- Year and Date
  2013-11-06 – 2013-11-07
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 最適合成順問題
- Author(s)
  河瀬康志，牧野和久，勢見賢人
- Organizer
  電子情報通信学会総合大会
- Place of Presentation
  新潟大学
- Year and Date
  2014-03-18 – 2014-03-21
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 制約充足問題に対する線形固定可能割当ての解析
- Author(s)
  木村慧，牧野和久
- Organizer
  日本オペレーションズ・リサーチ学会春季研究発表会
- Place of Presentation
  大阪大学
- Year and Date
  2014-03-06 – 2014-03-07
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 最適合成順問題
- Author(s)
  河瀬康志，牧野和久，勢見賢人
- Organizer
  日本オペレーションズ・リサーチ学会春季研究発表会
- Place of Presentation
  大阪大学
- Year and Date
  2014-03-06 – 2014-03-07
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 制約充足問題に対する線形固定可能割当ての解析
- Author(s)
  木村慧，牧野和久
- Organizer
  電子情報通信学会総合大会
- Place of Presentation
  新潟大学
- Year and Date
  2014-03-18 – 2014-03-21
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games
- Author(s)
  K. Makino
- Organizer
  8th Annual International Conference on Combinatorial Optimization and Applications
- Place of Presentation
  Hawaii, USA
- Year and Date
  2014-12-19 – 2014-12-21
- Data Source
  KAKENHI-PROJECT-25280004
[Presentation] 線形相補性問題の完全双対整数性
- Author(s)
  澄田範奈，垣村尚徳，牧野和久
- Organizer
  日本オペレーションズ・リサーチ学会春季研究発表会
- Place of Presentation
  大阪大学
- Year and Date
  2014-03-06 – 2014-03-07
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] オンラインナップサック問題に対する乱択アルゴリズム
- Author(s)
  Han Xin, 河瀬康志, 牧野和久
- Organizer
  日本オペレーションズ・リサーチ学会秋季研究発表会
- Place of Presentation
  徳島大学
- Year and Date
  2013-09-11 – 2013-09-12
- Data Source
  KAKENHI-PLANNED-24106002
[Presentation] 除去可能オンラインナップサック問題に対する乱択アルゴリズム
- Author(s)
  Han Xin, 河瀬康志, 牧野和久
- Organizer
  日本オペレーションズ・リサーチ学会「最適化の理論と応用」研究部会SOTA
- Place of Presentation
  筑波大学
- Year and Date
  2013-06-29 – 2013-06-30
- Data Source
  KAKENHI-PLANNED-24106002

1. FUJISHIGE Satoru (10092321)

# of Collaborated Projects: 6 results

# of Collaborated Products: 33 results
2. HIRAI Hiroshi (20378962)

# of Collaborated Projects: 3 results

# of Collaborated Products: 1 results
3. TAKABATAKE Takashi (50324827)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
4. IWATA Satoru (00263161)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
5. KIJIMA Shuji (70452307)

# of Collaborated Projects: 2 results

# of Collaborated Products: 5 results
6. IBARAKI Toshihide (50026192)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
7. TAMURA Akihisa (50217189)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
8. Watanabe Osamu (80158617)

# of Collaborated Projects: 2 results

# of Collaborated Products: 0 results
9. 高澤兼二郎 (10583859)

# of Collaborated Projects: 2 results

# of Collaborated Products: 1 results
10. YAGIURA Mutsunori (10263120)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
11. NAGAMOCHI Hiroshi (70202231)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
12. FUKUSHIMA Masao (30089114)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
13. SHIGENO Maiko (40272687)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
14. ASANO Takao (90124544)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
15. IMAI Hiroshi (80183010)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
16. TODA Seinosuke (90172163)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
17. MARUOKA Akira (50005427)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
18. MINATO Shinichi (10374612)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
19. KAWARABAYASHI Kazuhisa (40361159)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
20. ASANO Tetsuo (90113133)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
21. KATOH Naoki (40145826)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
22. AVIS David (90584110)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
23. TOKUYAMA Takeshi (40312631)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
24. YAMASHITA Shigeru (30362833)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
25. TAKIMOTO Eiji (50236395)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
26. HORIYAMA Takashi (60314530)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
27. MORI Ryuhei (60732857)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
28. 河村彰星 (20600117)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
29. 垣村尚徳 (30508180)

# of Collaborated Projects: 1 results

# of Collaborated Products: 15 results
30. 小林佑輔 (40581591)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
31. ロスマンベンジャミン (90599177)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
32. 谷川眞一 (30623540)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
33. 石井利昌 (30324487)

# of Collaborated Projects: 1 results

# of Collaborated Products: 3 results
34. 増山繁 (60173762)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
35. COOK Stephen

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
36. ZIEGLER Martin

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
37. GURVICH Vladimir

# of Collaborated Projects: 1 results

# of Collaborated Products: 7 results
38. BOROS Endre

# of Collaborated Projects: 1 results

# of Collaborated Products: 7 results
39. TAMAKI Suguru

# of Collaborated Projects: 0 results

# of Collaborated Products: 1 results
40. 小野廣隆

# of Collaborated Projects: 0 results

# of Collaborated Products: 1 results
41. 施建明

# of Collaborated Projects: 0 results

# of Collaborated Products: 1 results
42. 木村慧

# of Collaborated Projects: 0 results

# of Collaborated Products: 1 results

Makino Kazuhisa 牧野 和久

MAKINO Kazuhisa 牧野 和久

Research Projects

Research Products

Co-Researchers

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

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Institution

Development of efficient algorithms based on enumeration structuresPrincipal InvestigatorOngoing

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

劣モジュラ的な離散構造に注目した最適化基礎理論の展開と高速アルゴリズム開発Ongoing

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Exploring the limits of computation from mathematical logicPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Basic studies on discrete enumeration algorithmsPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

Studies on algorithms for large-scale discrete generation problemsPrincipal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

ブール理論に基づく離散システムの構造解析と計算限界の研究Principal Investigator

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

離散構造を有する列挙問題の解法に関する研究Principal Investigator

Principal Investigator

Project Period (FY)

Research Category

Research Field

Research Institution

ネットワークフロー問題に対する高速かつ実用的アルゴリズムに関する研究Principal Investigator

Principal Investigator

Project Period (FY)

Makino Kazuhisa 牧野和久

MAKINO Kazuhisa 牧野和久