組合せ最適化読書会 第12回

こんにちは。cosです。

今回は、第11章「重み付きマッチング」の前半でした。

内容は重み付きマッチングのアルゴリズムの概略、実装の下準備でした。
本の中で「多項式時間で解ける組合わせ最適化問題のうちで最も難しい問題の1つ」と書いてるだけあって内容はハードで、概略の段階で線形計画問題などが出てきたりもしました。
次回はアルゴリズムの実装の部分を読み進めていきます。