メンバー

TOP > メンバー > 小林 佑輔

小林 佑輔

名前 小林 佑輔 (Kobayashi, Yusuke)

准教授

E-Mail yusuke (emailアドレスには@kurims.kyoto-u.ac.jp をつけてください)


研究内容 離散最適化とアルゴリズムの研究

紹 介
離散最適化問題に対するアルゴリズムの理論研究を行なっている。特に,効率的に解ける問題(多項式時間で解ける問題)と難解な問題との本質的な差異がどこにあるのかを追究し,効率的に解ける問題の枠組みの構築,および各種問題に対するより効率的なアルゴリズムの設計・解析を行なっている。
代表的な研究としては,重み付き線形マトロイドパリティ問題に対する多項式時間アルゴリズムの設計が挙げられる。重み付き線形マトロイドパリティ問題は,重み付きマッチング問題と重み付き線形マトロイド交叉問題という離散最適化分野における代表的な二つの問題の共通の一般化として 1970 年代に導入され,統一的に数多くの問題を記述できることから注目を集めてきた。しかし,この問題に対しては非常に限られた結果しかこれまでに知られておらず,多項式時間アルゴリズムが存在するか否かは 40 年近くもの間未解決であった。我々の研究 [1] では,線形代数的定式化や増加道アルゴリズムといった重み無しの問題に使われていた手法を重み付きの問題に適用できる形に発展させるとともに,主双対アルゴリズムや組合せ緩和法といった手法を用いることで,この問題に対する初の多項式時間アルゴリズムを与えている。さらに,重み付き線形マトロイドパリティ問題が統一的に数多くの問題を記述できることから,本研究成果は副次的に様々な問題に対する多項式時間アルゴリズムを与えている。
また,ネットワークの頑健性・耐故障性をモデル化した最適化問題に対するアルゴリズムの研究も行なっている。文献 [2] は入力グラフの連結度にある種の仮定をおいた状況下での連結度増大問題を,文献 [3] は全体の連結性ではなく「いずれかの拠点と連結であること」を目的としたネットワークを設計する一般化ターミナルバックアップ問題を,文献 [4] は同時に複数のノードやリンクの損傷が起こる状況を考慮したモデルの上でネットワークの頑健性を評価する問題をそれぞれ扱っており,いずれも各問題に対して初めての多項式時間アルゴリズムを与えている。
上記以外にも,グラフマイナー理論に基づくアルゴリズムの設計 [5, 6, 7],有向木詰込み問題の一般化に関する研究 [8],効率的アルゴリズムに繋がる離散構造の研究 [9, 10] も行なっている。
  1. A weighted linear matroid parity algorithm, Proceedings of the 49th ACM Symposium on Theory of Computing (STOC 2017), 2017, pp. 264-276. (with S. Iwata)
  2. An algorithm for (n-3)-connectivity augmentation problem: jump system approach, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 565-587. (with K. Bérczi)
  3. The generalized terminal backup problem, SIAM Journal on Discrete Mathematics, 29 (2015), pp. 1764-1782. (with A. Bernáth and T. Matsuoka)
  4. Max-flow min-cut theorem and faster algorithms in a circular disk failure model, Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM 2014), 2014, pp. 1635-1643. (with K. Otsuki)
  5. Packing edge-disjoint odd Eulerian subgraphs through prescribed vertices in 4-edge-connected graphs, SIAM Journal on Discrete Mathematics, 31 (2017), pp. 766-782. (with N. Kakimura and K. Kawarabayashi)
  6. Edge-disjoint odd cycles in 4-edge-connected graphs, Journal of Combinatorial Theory, Series B, 119 (2016), pp. 12-27. (with K. Kawarabayashi)
  7. The disjoint paths problem in quadratic time, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 424-435. (with K. Kawarabayashi)
  8. Covering intersecting bi-set families under matroid constraints, SIAM Journal on Discrete Mathematics, 30 (2016), pp. 1758-1774. (with K. Bérczi and T. Király)
  9. A proof of Cunningham's conjecture on restricted subgraphs and jump systems, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 948-966. (with J. Szabó, and K. Takazawa)
  10. Even factors, jump systems, and discrete convexity, Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139-161. (with K. Takazawa)

← BACK TO THE TOP

← BACK TO THE TOP

  • Follow on

Research Institute for Mathematical Sciences (RIMS)