• Search Research Projects
  • Search Researchers
  • How to Use
  1. Back to previous page

Makino Kazuhisa  牧野 和久

ORCIDConnect your ORCID iD *help
… Alternative Names

MAKINO Kazuhisa  牧野 和久

Less
Researcher Number 60294162
Other IDs
External Links
Affiliation (Current) 2023: 京都大学, 数理解析研究所, 教授
Affiliation (based on the past Project Information) *help 2016 – 2023: 京都大学, 数理解析研究所, 教授
2011 – 2016: 京都大学, 数理解析研究所, 准教授
2013: 京都大学, 数理解析研究所, 准教授(Associate Professor)
2011: 東京大学, 情報理工学(系)研究科, 准教授
2007 – 2010: The University of Tokyo, Graduate School of Information and Technology, Associate Professor … More
2008: 東京大学, 大学院・情報理工学系・研究科, 准教授
2007: 東大, 情報理工学(系)研究科, 助教授
2005 – 2006: 東京大学, 大学院情報理工学系研究科, 助教授
2005: 東京大学, 大学院・情報理工学系研究科, 助教授
2001 – 2004: Grad. School of Engineering Science, Osaka Univ., Assoc. Prof., 基礎工学研究科, 助教授
2002 – 2003: 大阪大学, 大学院・基礎工学研究科, 助教授
2000: 大阪大学, 基礎工学研究科, 講師
1998 – 1999: Osaka Univ.Grad.School of Engineering Science, Assis.Prof., 基礎工学研究科, 助手
1998 – 1999: 大阪大学, 大学院・基礎工学研究科, 助手 Less
Review Section/Research Field
Principal Investigator
Fundamental theory of informatics / Science and Engineering / Medium-sized Section 60:Information science, computer engineering, and related fields / Transformative Research Areas, Section (IV) / Theory of informatics / 計算機科学 / Engineering fundamentals
Except Principal Investigator
Social systems engineering/Safety system / Medium-sized Section 61:Human informatics and related fields / Transformative Research Areas, Section (IV) … More / Science and Engineering / 社会システム工学 / System engineering / Mathematical informatics / Fundamental theory of informatics Less
Keywords
Principal Investigator
アルゴリズム / アルゴリズム論 / 計算量 / 列挙 / マトロイド / 施設配置問題 / オンライン問題 / 主双対法 / 固定パラメータ容易 / 正モジュラ … More / 組合せゲーム / 最適化 / 離散数学 / 計算複雑度 / 実数計算量 / 回路計算量 / 反マトロイド / computation / 双対性判定 / 信頼性 / ネットワーク / 一般化フロー / 強NP困難 / 近似アルゴリズム / ポリベーシック多面体 / 近似 / ラミナー / 連結度 / ソース配置問題 / 辺ランキング / フロー / 離散構造 / 仮設推論 / 列挙問題 / 準多項式時間 / 重みつき横断 / 双対化問題 / クリーク列挙 / 列挙アルゴリズム / 閉路 / 橋 / カット / 2部マッチング / ネットワークフロー / 多項式時間アルゴリズム / 仮説推論 / マッチング / モノポリー / データ分析 / 推論問題 / ホーン理論 / 拡大 / 論理関数 / 部分定義論理関数 / ホーンブール関数 / 推論 / 知識表現 / データマイニング … More
Except Principal Investigator
組合せ最適化 / 劣モジュラ関数 / アルゴリズム / 離散最適化 / Submodular Functions / Combinatorial Optimization / Discrete Optimization / Algorithms / 数理計画 / 計算限界解明 / アルゴリズム理論 / 実験経済学 / 機械学習 / 最適化 / 人工知能 / ゲーム理論 / 研究推進 / 組織運営 / 革新的アルゴリズム基盤 / 啓発活動 / 若手育成 / 成果のとりまとめ / 計算限界 / 研究成果とりまとめ / ELC Workshop / ELC Seminar / ELC 秋学校 / 計算理論若手研究者育成 / 計算限界研究センター / 多視点からの統合的解析 / 若手研究者育成 / 各種啓発・研究成果波及 / 国際研究者交流 / 多視点からの連携研究 / 計算限界解明手法の開拓 / 成果の総括と公表 / 計算量上下界解析 / 計算複雑さの理論 / 成果の波及 / 成果の総括 / 若手研究者の育成 / 研究拠点形成 / 研究連携促進 / Mathematical Programming / Large-Seal Systems / 大規模システム / Hypergraphs / コテリ理論 / ネットワーク最適化 / 計算効率 / ハイパーグラフ / combinatorial optimization / CSP (constraint satisfaction problem) / metaheuristics / problem solving engine / メタ・ヒューリスティックス / 組合セアルゴリズム / 問題解決 / 一般化割当問題 / 制約充足問題 / タブ-探索 / 組合せアルゴリズム / CSP(制約充足問題) / メタヒューリスティクス / 問題解決エンジン / 劣モジュラ構造 / 離散アルゴリズム / 脱乱択化 / マルコフ連鎖 / 細合せ最滴化 / OR Less
  • Research Projects

    (21 results)
  • Research Products

    (176 results)
  • Co-Researchers

    (54 People)
  •  アルゴリズム基礎理論の追究・発展Principal Investigator

    • Principal Investigator
      牧野 和久
    • Project Period (FY)
      2020 – 2024
    • Research Category
      Grant-in-Aid for Transformative Research Areas (A)
    • Review Section
      Transformative Research Areas, Section (IV)
    • Research Institution
      Kyoto University
  •  Research Initiatives on Algorithmic Foundations for Social Advancement

    • Principal Investigator
      湊 真一
    • Project Period (FY)
      2020 – 2024
    • Research Category
      Grant-in-Aid for Transformative Research Areas (A)
    • Review Section
      Transformative Research Areas, Section (IV)
    • Research Institution
      Kyoto University
  •  Creation of Incentive Design Science

    • Principal Investigator
      横尾 真
    • Project Period (FY)
      2020 – 2022
    • Research Category
      Grant-in-Aid for Scientific Research (A)
    • Review Section
      Medium-sized Section 61:Human informatics and related fields
    • Research Institution
      Kyushu University
  •  局所構造を利用した高速なアルゴリズムの開発Principal Investigator

    • Principal Investigator
      牧野 和久
    • Project Period (FY)
      2019 – 2022
    • Research Category
      Grant-in-Aid for 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 Investigator

    • Principal Investigator
      Makino Kazuhisa
    • Project Period (FY)
      2014 – 2019
    • Research Category
      Grant-in-Aid for Scientific Research (B)
    • Research Field
      Theory of informatics
    • Research Institution
      Kyoto University
  •  Developments of discrete optimization theory and efficient algorithms based on submodular structures

    • Principal Investigator
      Fujishige Satoru
    • 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

All 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 Other

All Journal Article Presentation Book

  • [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] Posimodular Function Optimization2022

    • Author(s)
      Magnus M. Halldorsson, Toshimasa Ishii, Kazuhisa Makino, Kenjiro Takazawa
    • Journal Title

      Algorithmica

      Volume: 84 Issue: 4 Pages: 1107-1131

    • DOI

      10.1007/s00453-021-00910-y

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-16K00001, KAKENHI-PROJECT-20K11699, KAKENHI-PROJECT-19K22841
  • [Journal Article] Online Scheduling on Identical Machines with a Metric State Space2022

    • Author(s)
      Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita
    • Journal Title

      LIPICS STACS2022

      Volume: 219

    • Peer Reviewed / Open Access
    • Data Source
      KAKENHI-PROJECT-19K22841
  • [Journal Article] Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties and Incomplete Lists2022

    • Author(s)
      Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi
    • Journal Title

      LIPICS STACS2022

      Volume: 219

    • Peer Reviewed / Open Access
    • Data Source
      KAKENHI-PROJECT-19K22841
  • [Journal Article] Generating clause sequences of a CNF formula2021

    • Author(s)
      Kristof Berczi, Endre Boros, Ondrej Cepek, Khaled M. Elbassioni, Petr Kucera, Kazuhisa Makino
    • Journal Title

      Theor. Comput. Sci.

      Volume: 856 Pages: 68-74

    • DOI

      10.1016/j.tcs.2020.12.021

    • Peer Reviewed / Open Access / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-19K22841, KAKENHI-PROJECT-20H00609
  • [Journal Article] Optimal Matroid Partitioning Problems2021

    • Author(s)
      Kawase Yasushi, Kimura Kei, Makino Kazuhisa, Sumita Hanna
    • Journal Title

      Algorithmica

      Volume: - Issue: 6 Pages: 1653-1676

    • DOI

      10.1007/s00453-021-00797-9

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-17K12646, KAKENHI-PROJECT-20H00609
  • [Journal Article] Approximating minimum representations of key Horn functions2020

    • Author(s)
      Krisof Berczi, Endre Boros, Ondrej Cepek, Petr Kucera, Kazuhisa Makino
    • Journal Title

      International Symposium on Artificial Intelligence and Mathematics

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-19K22841
  • [Journal Article] Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices2020

    • Author(s)
      Khaled M. Elbassioni, Kazuhisa Makino
    • Journal Title

      SIAM J. Discret. Math.

      Volume: 34 Issue: 1 Pages: 843-864

    • DOI

      10.1137/18m1198995

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-19K22841
  • [Journal Article] The Steiner Problem for Count Matroids2020

    • Author(s)
      Tibor Jordan, Yusuke Kobayashi, Ryoga Mahara, Kazuhisa Makino
    • Journal Title

      Lecture Notes in Computer Science

      Volume: 12126 Pages: 330-342

    • DOI

      10.1007/978-3-030-48966-3_25

    • ISBN
      9783030489656, 9783030489663
    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-19K22841, KAKENHI-PROJECT-20H00609
  • [Journal Article] : Online Knapsack Problems with a Resource Buffer2019

    • Author(s)
      Xin Han, Yasushi Kawase, Kazuhisa Makino, Haruki Yokomaku
    • Journal Title

      ISAAC2019, LIPIcs

      Volume: 149

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Total dual integrality of the linear complementarity problem2019

    • Author(s)
      Hanna Sumita, Naonori Kakimura, Kazuhisa Makino
    • Journal Title

      Annals of Operations Research

      Volume: 274 Issue: 1-2 Pages: 531-553

    • DOI

      10.1007/s10479-018-2926-8

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Online Knapsack Problems with a Resource Buffer2019

    • Author(s)
      Xin Han, Yasushi Kawase, Kazuhisa Makino, Haruki Yokomaku
    • Journal Title

      ISAAC 2019, LIPIcs

      Volume: 149

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-19K22841
  • [Journal Article] Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs2019

    • Author(s)
      Khaled M. Elbassioni, Kazuhisa Makino
    • Journal Title

      ESA 2019, LIPIcs

      Volume: 144

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-19K22841
  • [Journal Article] Sprague-Grundy function of symmetric hypergraphs.2019

    • Author(s)
      Endre Boros, Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, Peter Mursic
    • Journal Title

      J. Comb. Theory, Ser. A

      Volume: 165 Pages: 176-186

    • DOI

      10.1016/j.jcta.2019.02.006

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Khaled M. Elbassioni, Kazuhisa Makino, Waleed Najy: A Multiplicative Weight Updates Algorithm for Packing and Covering Semi-infinite Linear Programs2019

    • Author(s)
      Khaled M. Elbassioni, Kazuhisa Makino, Waleed Najy
    • Journal Title

      Algorithmica

      Volume: 81 Issue: 6 Pages: 2377-2429

    • DOI

      10.1007/s00453-018-00539-4

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Proportional cost buyback problem with weight bounds2019

    • Author(s)
      Yasushi Kawase, Xin Han, Kazuhisa Makino
    • Journal Title

      Theor. Comput. Sci.

      Volume: 774 Pages: 51-64

    • DOI

      10.1016/j.tcs.2016.06.005

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Sprague-Grundy function of matroids and related hypergraphs.2019

    • Author(s)
      Endre Boros, Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, Peter Mursic
    • Journal Title

      Theor. Comput. Sci.

      Volume: 799 Pages: 40-58

    • DOI

      10.1016/j.tcs.2019.09.041

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Online knapsack problem under concave functions2019

    • Author(s)
      Xin Han, Qinyang Chen, Kazuhisa Makino
    • Journal Title

      Theor. Comput. Sci.

      Volume: 786 Pages: 88-95

    • DOI

      10.1016/j.tcs.2018.03.025

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-19K22841, KAKENHI-PROJECT-26280001
  • [Journal Article] Surrogate optimization for p-norms2019

    • Author(s)
      Yasushi Kawase, Kazuhisa Makino
    • Journal Title

      Discrete Optimization

      Volume: 34 Pages: 100546-100546

    • DOI

      10.1016/j.disopt.2019.05.003

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions2019

    • Author(s)
      Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino
    • Journal Title

      Inf. Comput.

      Volume: 267 Pages: 74-95

    • DOI

      10.1016/j.ic.2019.03.005

    • NAID

      110009820595

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs2019

    • Author(s)
      Khaled M. Elbassioni, Kazuhisa Makino
    • Journal Title

      ESA2019, LIPIcs

      Volume: 144

    • Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Linear Satisfiability Preserving Assignments (Extended Abstract)2018

    • Author(s)
      Kei Kimura, Kazuhisa Makino
    • Journal Title

      IJCAI

      Volume: - Pages: 5622-5626

    • DOI

      10.24963/ijcai.2018/797

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions2018

    • Author(s)
      Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey
    • Journal Title

      Algorithmica

      Volume: 80 Issue: 11 Pages: 3132-3157

    • DOI

      10.1007/s00453-017-0372-7

    • NAID

      120006551768

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices2018

    • Author(s)
      Khaled M. Elbassioni, Kazuhisa Makino
    • Journal Title

      LIPIcs

      Volume: 101

    • DOI

      10.4230/LIPIcs.SWAT.2018.18

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] On the Sprague Grundy function of Exact k-Nim2018

    • Author(s)
      Endre Boros, Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, Peter Mursic
    • Journal Title

      Discrete Applied Mathematics

      Volume: 239 Pages: 1-14

    • DOI

      10.1016/j.dam.2017.08.007

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Parameterized edge Hamiltonicity2018

    • Author(s)
      M. Lampis, K. Makino, V. Mitsou and Y. Uno.
    • Journal Title

      Discrete Applied Mathematics

      Volume: 248 Pages: 68-78

    • DOI

      10.1016/j.dam.2017.04.045

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-17K00017, KAKENHI-PROJECT-26280001
  • [Journal Article] Unit Cost Buyback Problem2018

    • Author(s)
      Kawase Yasushi、Han Xin、Makino Kazuhisa
    • Journal Title

      Theory of Computing Systems

      Volume: - Issue: 6 Pages: 1-22

    • DOI

      10.1007/s00224-018-9897-7

    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-16K16005, KAKENHI-PROJECT-26280001
  • [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

    • ISBN
      9783319596044, 9783319596051
    • 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 Issue: 1 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

    • NAID

      130008061497

    • 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

      Lecture Notes in Computer Science, Algorithms and Data Structures

      Volume: 10389 Pages: 437-448

    • DOI

      10.1007/978-3-319-62127-2_37

    • ISBN
      9783319621265, 9783319621272
    • 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: 掲載確定 Issue: 1 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 Issue: 8 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

    • ISBN
      9783662557501, 9783662557518
    • 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

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Online minimization knapsack problem2016

    • Author(s)
      X. Han and K. Makino
    • Journal Title

      Theoretical Computer Science

      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×22×2 subgames2016

    • Author(s)
      Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino, Vladimir Oudalov
    • Journal Title

      International Journal of Game Theory

      Volume: 45 Issue: 4 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

    • 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

    • ISBN
      9783319517407, 9783319517414
    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001
  • [Journal Article] Randomized Algorithms for Online Knapsack Problems2015

    • Author(s)
      Xin Han, Yasushi Kawase, Kazuhisa Makino
    • Journal Title

      Theoretical Computer Science

      Volume: 562 Pages: 395-405

    • DOI

      10.1016/j.tcs.2014.10.017

    • NAID

      110009888067

    • 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

      Leibniz International Proceedings in Informatics

      Volume: 43 Pages: 355-364

    • DOI

      10.4230/LIPIcs.IPEC.2015.355

    • Peer Reviewed / Acknowledgement Compliant / Open Access / 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 Struct. Algorithms

      Volume: 46 Issue: 4 Pages: 739-761

    • DOI

      10.1002/rsa.20533

    • NAID

      110008583103

    • 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

      COCOA 2015:

      Volume: LNCS9486 Pages: 794-808

    • DOI

      10.1007/978-3-319-26626-8_59

    • ISBN
      9783319266251, 9783319266268
    • 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

      Mathematics of Operations Research

      Volume: 40 Issue: 4 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

    • ISBN
      9783662480533, 9783662480540
    • Peer Reviewed / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-26280001, KAKENHI-PLANNED-24106002
  • [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 Issue: 2 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

      LIPIcs

      Volume: 30 Pages: 103-115

    • DOI

      10.4230/LIPIcs.STACS.2015.103

    • 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 Issue: 1 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

      10.1007/978-3-319-12691-3

      Volume: 8881 Pages: 694-709

    • DOI

      10.1007/978-3-319-12691-3_52

    • ISBN
      9783319126906, 9783319126913
    • 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

    • ISBN
      9783319123394, 9783319123400
    • Peer Reviewed / Int'l Joint Research
    • Data Source
      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 Issue: 4 Pages: 357-362

    • 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

    • ISBN
      9783642387555, 9783642387562
    • 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

    • ISBN
      9783642450297, 9783642450303
    • 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 Issue: 2 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_30

    • ISBN
      9783642382321, 9783642382338
    • 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 Journal on Discrete Mathematics

      Volume: 27 Issue: 3 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] Augmenting edge-connectivity between vertex subsets2013

    • Author(s)
      T. Ishii,K. Makino
    • Journal Title

      Algorithmica

      Volume: - Issue: 1 Pages: 130-147

    • DOI

      10.1007/s00453-012-9724-5

    • NAID

      110007081988

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-23310098, KAKENHI-PROJECT-24700001, 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 J. Discrete Math.

      Volume: 27 Issue: 3 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

    • NAID

      110009820595

    • ISBN
      9783642392054, 9783642392061
    • 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

    • ISBN
      9783642387678, 9783642387685
    • 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: 未定 Issue: 2 Pages: 112-124

    • DOI

      10.1007/s00453-012-9741-4

    • Peer Reviewed
    • Data Source
      KAKENHI-PROJECT-22240001, KAKENHI-PROJECT-22500007, KAKENHI-PROJECT-23700015, 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 Issue: 3 Pages: 469-483

    • DOI

      10.1007/s13160-012-0075-z

    • NAID

      10031126878

    • 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 Trans. Comput. Log

      Volume: 13(3) Issue: 3 Pages: 23-23

    • DOI

      10.1145/2287718.2287723

    • NAID

      110006343679

    • 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

    • NAID

      120003338848

    • 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 Issue: 18 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 Issue: 2 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

    • NAID

      110002811978

    • 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

    • NAID

      110002811978

    • 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

    • NAID

      110002545917

    • 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 Issue: 11 Pages: 2004-2019

    • DOI

      10.1016/j.dam.2007.04.016

    • NAID

      110002811978

    • 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

    • NAID

      110002545917

    • 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 Issue: 4 Pages: 555-583

    • DOI

      10.1007/s00453-007-9012-y

    • NAID

      110002545917

    • 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

    • NAID

      110002545917

    • 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

    • NAID

      110002545917

    • 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

    • NAID

      110006343679

    • 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

    • NAID

      110002811978

    • 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

    • NAID

      110002811977

    • 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

    • NAID

      110002811977

    • 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

    • NAID

      110002811977

    • 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

    • NAID

      110002545917

    • 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

    • NAID

      110002545917

    • 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

    • NAID

      110002811977

    • 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 (掲載予定)

    • NAID

      110002811977

    • 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

    • NAID

      110001868875

    • 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

    • NAID

      110001868875

    • 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

    • NAID

      110002811978

    • 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

    • NAID

      110002812429

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

    • NAID

      110008583103

    • 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 (掲載予定)

    • NAID

      110002811977

    • Data Source
      KAKENHI-PROJECT-16310111
  • [Presentation] Monotone Dualization and Related Topics2020

    • Author(s)
      Kazuhisa Makino
    • Organizer
      The Fourteenth International Frontiers of Algorithmics Workshop
    • Invited / Int'l Joint Research
    • Data Source
      KAKENHI-PROJECT-19K22841
  • [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.  TAMURA Akihisa (50217189)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 0 results
  • 4.  TAKIMOTO Eiji (50236395)
    # of Collaborated Projects: 3 results
    # of Collaborated Products: 0 results
  • 5.  TAKABATAKE Takashi (50324827)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 6.  IWATA Satoru (00263161)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 7.  KIJIMA Shuji (70452307)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 4 results
  • 8.  IBARAKI Toshihide (50026192)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 9.  Watanabe Osamu (80158617)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 10.  MINATO Shinichi (10374612)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 11.  KAWARABAYASHI Kazuhisa (40361159)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 12.  YAMASHITA Shigeru (30362833)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 13.  HORIYAMA Takashi (60314530)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 14.  河村 彰星 (20600117)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 15.  高澤 兼二郎 (10583859)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 0 results
  • 16.  玉置 卓 (40432413)
    # of Collaborated Projects: 2 results
    # of Collaborated Products: 1 results
  • 17.  YAGIURA Mutsunori (10263120)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 18.  NAGAMOCHI Hiroshi (70202231)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 19.  FUKUSHIMA Masao (30089114)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 20.  SHIGENO Maiko (40272687)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 21.  ASANO Takao (90124544)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 22.  IMAI Hiroshi (80183010)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 23.  TODA Seinosuke (90172163)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 24.  MARUOKA Akira (50005427)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 25.  ASANO Tetsuo (90113133)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 26.  KATOH Naoki (40145826)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 27.  AVIS David (90584110)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 28.  TOKUYAMA Takeshi (40312631)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 29.  MORI Ryuhei (60732857)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 30.  垣村 尚徳 (30508180)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 12 results
  • 31.  小林 佑輔 (40581591)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 1 results
  • 32.  ロスマン ベンジャミン (90599177)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 33.  谷川 眞一 (30623540)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 34.  増山 繁 (60173762)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 35.  石井 利昌 (30324487)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 4 results
  • 36.  小野 廣隆 (00346826)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 1 results
  • 37.  定兼 邦彦 (20323090)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 38.  渋谷 哲朗 (60396893)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 39.  木村 慧 (00758716)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 1 results
  • 40.  宇野 毅明 (00302977)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 41.  安田 宜仁 (50396149)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 42.  上原 隆平 (00256471)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 43.  横尾 真 (20380678)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 44.  神取 道宏 (10242132)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 45.  関口 格 (20314461)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 46.  川越 敏司 (80272277)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 47.  鹿島 久嗣 (80545583)
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 48.  COOK Stephen
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 49.  ZIEGLER Martin
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 0 results
  • 50.  GURVICH Vladimir
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 4 results
  • 51.  BOROS Endre
    # of Collaborated Projects: 1 results
    # of Collaborated Products: 4 results
  • 52.  澄田 範奈
    # of Collaborated Projects: 0 results
    # of Collaborated Products: 1 results
  • 53.  宇野 裕之
    # of Collaborated Projects: 0 results
    # of Collaborated Products: 1 results
  • 54.  河瀬 康志
    # of Collaborated Projects: 0 results
    # of Collaborated Products: 1 results

URL: 

Are you sure that you want to link your ORCID iD to your KAKEN Researcher profile?
* This action can be performed only by the researcher himself/herself who is listed on the KAKEN Researcher’s page. Are you sure that this KAKEN Researcher’s page is your page?

この研究者とORCID iDの連携を行いますか?
※ この処理は、研究者本人だけが実行できます。

Information User Guide FAQ News Terms of Use Attribution of KAKENHI

Powered by NII kakenhi