経済学と関わりの深い代表的な組合せ問題として安定マッチング問題がある．近年，経済学分野のみならず，人工知能分野や理論計算機科学分野において，安定マッチング問題を一般化した効用関数付きグラフ最適化問題が注目されつつある．効用関数付きグラフ最適化問題は，コミュニティ検出，人員割当，配置割当など様々な応用があるが，モデルにおける複数の望ましい解概念，効用関数，選好，グラフ構造など複数の要素を持つため解を求めることが困難な場合も多い．そこで，本研究では，従来のグラフ最適化問題とは異なる効用関数付きグラフ最適化問題に対して，高性能アルゴリズム設計及び計算量解析を行う．
