講義資料

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

スライド

  1. 多面体的組合せ論

    • 組合せ最適化とは

    • 線形計画の復習

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

  2. 二部マッチング①

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

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

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

  3. 二部マッチング②

    • 最短路問題

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

    • 最適性条件からの見方

  4. 最大流①

    • 最大流問題

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

  5. 最大流②

    • Ford–Fulkerson 法

    • Edmonds–Karp 法

  6. 最小費用流

    • 最小費用流問題

    • アルゴリズム

  7. マトロイド

    • マトロイドとは

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

    • マトロイド多面体

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

    • 独立マッチング

    • サーキット

    • アルゴリズム

  9. 劣モジュラ最小化 [補足資料]

    • 劣モジュラ関数の例

    • Lovász拡張

    • 最小ノルム点法

  10. 劣モジュラ最大化

    • 定式化

    • モデリング例

    • 貪欲法

Githubリポジトリ

https://github.com/tasusu/tokuron

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

スライド

Githubリポジトリ

https://github.com/tasusu/keisansuuri

東大計数 演習第二2019 (Multiplicative Weight Update)

東大計数 演習第二2018 (完全マッチングに対する代数的アルゴリズム)