所員 -牧野 和久-

名前 牧野 和久 (Makino, Kazuhisa)
准教授
E-Mail makino (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)
U R L
研究内容 離散最適化とアルゴリズムの研究
紹 介
 グラフ理論、あるいは、組合せ論などの離散的な構造を解析する研究、あるいは,それらの構造を利用した最適化やアルゴリズムの研究を行っている。
 代表的な研究としては、単調な論理関数の双対化問題を研究している[1]。単調な論理関数の双対化問題とは、与えられた論理積形からそれと等価な単調な論理和形を求める問題であり、数理計画,人工知能,データベース,分散システム,学習理論など様々な分野に現れる数多くの重要かつ実用的な問題と(多項式時間還元の意味で)等価であることが知られている.1996 年にFredmanとKhachiyan による準多項式時間で解けることは示されているが、未だに多項式時間で解けるかどうかわかっていない。この双対化問題は,この問題は、単調論理関数の論理積形、論理和形という2つの双対的な表現が与えられたときに、それらが等価であるかを判定する問題と等価であり、人工知能分野において重要な役割をもつホーン理論におけるホーンルールと特性ベクトル集合という双対表現の等価性とも関連する[2]。また、列挙分野においてその計算量が未解決であった多くの問題がこの双対化問題に準多項式帰着可能であることがわかってきた[3,4]。
 また、推論分野における論理仮説の補完問題に対して、広く信じられていた予想を覆し、最も重要なクラスであるホーン推論において、逐次多項式時間で可能であることを示した[5]
 上記以外にも、整数線形不等式系[6]、相補性問題[7]、オンライン最適化問題[8]、ロバスト最適化[9]、ゲーム理論における均衡解に関する研究[10] などを行っている。
  1. New Results on Monotone Dualization and Generating Hypergraph Transversals, SIAM Journal on Computing, 32 (2003) 514-537 (with T. Eiter and G. Gottlob)
  2. Computing Intersections of Horn Theories for Reasoning with Models, Artifical Intelligence 110(1999) 57-101. (with T. Eiter and T. Ibaraki)
  3. Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities, SIAM Journal on Computing 31 (2002) 1624-1643. (with E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan)
  4. Dual-Bounded Generating Problems: Efficient and Inefficient Points for Discrete Probability Distributions and Sparse Boxes for Multidimen- sional Data, Theorical Computer Science 379 (2007) 361-376. (with L. Khachiyan, E. Boros, K. Elbassioni, and V. Gurvich)
  5. On Computing All Abductive Explanations from a Propositional Horn Theory, Journal of the ACM 54 (5) (2007). (with T. Eiter)
  6. Trichotomy for Integer Linear Systems Based on Their Sign Patterns, STACS 2012. (with K. Kimura)
  7. Sparse Linear Complementarity Problems, CIAC 2013. (with H. Sumita, N. Kakimura).
  8. Online Removable Knapsack with Limited Cuts. Theoretical Computer Science 411 (2010) 3956-3964, (with X. Han).
  9. Robust Independence Systems, ICALP (2011) 367-378. (with N. Kakimura)
  10. A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions, ICALP (2013). (with E. Boros, K. Elbassioni, and V. Gurvich)