講義資料

総研大 統計科学コース 組合せ最適化特論

各回内容・スライド

  1. 多面体的組合せ論

    • 組合せ最適化とは

    • 線形計画の復習

    • 整数多面体，完全単模行列

  2. 二部マッチング①

    • 二部マッチングの最大最小定理

    • 重みなし二部マッチング

    • 重み付き二部マッチング

  3. 二部マッチング②

    • 最短路問題

    • 逐次最短路法と主双対法

    • 最適性条件からの見方

  4. 最大流①

    • 最大流問題

    • 最大流を用いたモデリング

  5. 最大流②

    • Ford–Fulkerson 法

    • Edmonds–Karp 法

  6. 最小費用流

    • 最小費用流問題

    • アルゴリズム

  7. マトロイド

    • マトロイドとは

    • 最小重み独立集合と貪欲法

    • マトロイド多面体

  8. 独立マッチング・マトロイド交差

    • 独立マッチング

    • サーキット

    • アルゴリズム

  9. 劣モジュラ最小化

    • 劣モジュラ関数の例

    • Lovász拡張

    • 最小ノルム点法

  10. 劣モジュラ最大化

    • 定式化

    • モデリング例

    • 貪欲法

  11. 精選トピック① 完全マッチングに対する代数的アルゴリズム

  12. 精選トピック② Multiplicative Weight Update

  13. 精選トピック③ グラフのスペクトル疎化

Githubリポジトリ

https://github.com/tasusu/tokuron

総研大 統計科学コース 計算数理基礎（相馬担当分「組合せ最適化」）

スライド

English slides

Githubリポジトリ

https://github.com/tasusu/keisansuuri

東大 計数工学科 数理情報工学演習第二

2019 (Multiplicative Weight Update)

2016–2018 (完全マッチングに対する代数的アルゴリズム)