制約つき単調劣モジュラ関数最大化とその応用

藤井海斗

（指導教員：岩田覚教授／ 数理情報第7研究室）

研究概要

さまざまな制約のもとでの単調劣モジュラ関数最大化問題が近年注目されている．本研究では，b-マッチング制 約に対して近似アルゴリズムを二つ提案し，その近似比について理論的な保証を与えた．また，応用に関する計算機実験もおこなっ た．

アルゴリズムのイメージ

卒論の感想

いろいろな体験ができて楽しい半年間になりました．指導してくださった岩田先生と数理7研のみなさまに感謝い たします．